#P5779. [NOI2022] 树上邻域数点

    ID: 4780 传统题 3000ms 2048MiB 尝试: 7 已通过: 1 难度: 10 上传者: 标签>数据结构排序与序列处理倍增图论动态规划CF3500分治线段树交互

[NOI2022] 树上邻域数点

「NOI2022」树上邻域数点

Hydro 提交说明

这是一道函数交互题。

请选择 GNU C++17,在源代码中包含 #include "count.h",只实现题目要求的函数,不要自行编写 main。平台自动提供已适配的头文件与主程序。

题目描述

给出五元组 (T,I,SV,SE,ι)(T, I, S_V, S_E, \iota),其中:

  • TT 是一棵 nn 个点的有根树 T=(V,E)T = (V, E),其中 VV 为 TT 的点集,EE 为 TT 的边集。树的节点被编号为 1,2,…,n1, 2, \ldots, n,其中根节点编号为 11。
  • II 是一个集合,集合中的元素称作信息。其中有两个不同的特殊元素:单位元 ϵ\epsilon 和不合法信息 ⊥\bot。

对于一般的信息,其都具有点集合和边集合两个属性。特别的,对于单位元,其只有边集合;不合法信息没有点集合和边集合。

  • 对于信息 o∈I∖{ϵ,⊥}o \in I \setminus \{ \epsilon, \bot \},oo 的点集合是 VV 的一个二元子集,记作 SV(o)S_V(o),满足 SV(o)⊆VS_V(o) \subseteq V 且 ∣SV(o)∣=2\lvert S_V(o) \rvert = 2。其中,两个集合 A,BA, B 的差 A∖BA \setminus B 被定义为 $A \setminus B = \{ x \in A \hspace{3mu}\vert\hspace{3mu} x \notin B \}$。
  • 对于信息 o∈I∖{⊥}o \in I \setminus \{ \bot \},oo 的边集合是 EE 的一个子集,记作 SE(o)S_E(o),满足 SE(o)⊆ES_E(o) \subseteq E。规定单位元的边集合为空,也即 SE(ϵ)=∅S_E(\epsilon) = \varnothing。
  • 对于树上的任何一条边 e∈Ee \in E,记 e=(u,v)e = (u, v),存在一个关于 ee 的信息 ι(e)∈I\iota(e) \in I,它以其端点为点集合、自身为边集合,即 SV(ι(e))={u,v}S_V(\iota(e)) = \{ u, v \}、SE(ι(e))={e}S_E(\iota(e)) = \{ e \}。

信息有两种合并的方式,分别记作 RR 和 CC。对于 ∀a,b∈I\forall a, b \in I,记 r=R(a,b),c=C(a,b)r = R(a, b), c = C(a, b),满足 r,c∈Ir, c \in I,则:

  • 单位元和任何信息合并都得到对方。也即,如果 a=ϵa = \epsilon,那么 r=c=br = c = b;如果 b=ϵb = \epsilon,那么 r=c=ar = c = a。
  • 不合法信息和任何信息合并都得到不合法信息。也即,如果 a=⊥a = \bot 或者 b=⊥b = \bot,那么 r=c=⊥r = c = \bot。
  • 对于剩下的情况,如果两个信息的边集合的交集非空,或者点集合的交集的大小不为 11,则合并得到不合法信息。也即,如果 SE(a)∩SE(b)≠∅S_E(a) \cap S_E(b) \ne \varnothing 或 ∣SV(a)∩SV(b)∣≠1\lvert S_V(a) \cap S_V(b) \rvert \ne 1,则 r=c=⊥r = c = \bot。
  • 否则,有SE(r)=SE(c)=SE(a)∪SE(b),S_E(r) = S_E(c) = S_E(a) \cup S_E(b) \text{,} SV(r)=SV(a),S_V(r) = S_V(a) \text{,} SV(c)=SV(a)⊕SV(b),S_V(c) = S_V(a) \oplus S_V(b) \text{,} 其中 ⊕\oplus 表示集合的对称差运算,也即 A⊕B=(A∪B)∖(A∩B)A \oplus B = (A \cup B) \setminus (A \cap B)。

定义 TT 中两个点的树上距离为树上以两个点为端点的唯一简单路径经过的边数。

给出评分参数 MM 和 qq 次询问,每次询问给出树上的一个点 uu 和一个非负整数 dd。记点集 XX 为 TT 中所有与 uu 的树上距离不超过 dd 的点构成的集合,又记边集 $Y = \{ (a, b) \in E \hspace{3mu}\vert\hspace{3mu} a, b \in X \}$ 为 XX 内部的边集。可以证明,从 ϵ\epsilon 和所有 ι(e)\iota(e)(e∈Ee \in E)出发,总是能通过有限次 R,CR, C 的调用得到信息 o≠⊥o \ne \bot 满足 SE(o)=YS_E(o) = Y。

每组询问中,你需要在 RR 和 CC 的调用次数总和不超过 MM 的限制下构造出一个满足这样的要求的信息 oo。特别地,如果 d=0d = 0,则直接返回单位元 ϵ\epsilon 即可。

实现细节

请确保你的程序开头有 #include "count.h"。

头文件 count.h 中实现了如下内容:

  1. 定义了信息对应的数据类型 info;

  2. 定义了 ϵ\epsilon 所对应的 info 类型常量 emptyinfo,你可以在程序中直接使用。

  3. 定义并实现了以下两个信息合并函数,你可以在程序中直接调用:

    info MR(info a,info b);
    info MC(info a,info b);
    
    • 两个函数分别返回 R(a,b)R(a, b) 与 C(a,b)C(a, b) 对应的信息。

    你需要保证调用 R(a,b)\boldsymbol{R(a, b)} 或 C(a,b)\boldsymbol{C(a, b)} 时结果不为 ⊥\boldsymbol{\bot},否则程序可能会出现异常行为。

  4. 定义并实现了判定一个信息是否为单位元的函数,你可以在程序中直接调用:

    bool isempty(info a);
    
    • 这个函数返回真当且仅当 aa 为单位元。

可以查看参考交互库了解更多实现细节。

你不需要,也不应该实现主函数。 你需要实现如下几个函数:

void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);
  • T 表示测试点编号,n 表示树的点数,q 表示询问数,M 表示该测试点的评分参数。
  • fa 和 e 的长度均为 n−1n - 1。对于 0≤i<n−10 \le i < n - 1,fa[i]fa[i] 和 i+2i + 2 为第 ii 条边 eie_i 的两个端点,e[i]e[i] 为题目描述中提到的 ι(ei)\iota(e_i) 所对应的 info 类型元素。数据保证 fa[i]fa[i] 小于 i+2i + 2。
info ask(int u, int d);

给出一个询问,参数的意义见题目描述。你需要在函数结束时返回一个满足题设条件的信息。

原赛最终测试时,在每个测试点,交互库会恰好调用一次 init 函数,随后调用 qq 次 ask 函数。交互库会使用特殊的实现方式,单个 info 类型的变量会恒定消耗 1212 字节内存,这与下发的参考交互库不同。为保证程序运行时内存使用在题目限制内,你需要保证运行过程中没有过多的 info 类型变量同时存在。

保证在满足调用次数限制且不进行 isempty 函数调用的情况下,最终测试的交互库运行所需的时间不超过 0.6 秒,交互库本身所消耗的内存不超过 16 MiB。保证在只执行 108{10}^8 次 isempty 函数调用的情况下,最终测试的交互库运行的时间不超过 0.25 秒。

测试程序方式

Hydro 版 count.h包含测试主程序。在同一目录放置 count.h 与你的 count.cpp,可用下面的命令编译:

g++ -std=c++17 -O2 count.cpp -o count

本地测试主程序从标准输入读入:

  • 第一行四个整数 T,n,q,MT,n,q,M,依次表示测试点编号、点数、询问数和评分参数。
  • 第二行 n−1n-1 个整数 p2,p3,…,pnp_2,p_3,\ldots,p_n,依次表示点 22 至 nn 的父节点。每个 pip_i 满足 1≤pi<i1\le p_i<i。
  • 接下来 qq 行,每行两个整数 u,du,d,表示一次询问。

Hydro 版测试主程序对每次询问输出一行 ask 返回信息的校验值。检测到非法操作或超过调用次数限制时,主程序会输出错误信息。

原赛参考交互库

原赛附件包含示例 count.cpp、原版 count.h、两份参考库和四组样例输入。使用 grader.o 时保留原头文件中的 GRADER 定义;使用 checker.o 时启用 CHECKER 并注释掉 GRADER。原赛使用 C++14 编译参赛源文件并链接所选的参考库。

原赛参考库接受与上面相同的调试输入。成功时输出一行三个统计量 C1,C2,C3C_1,C_2,C_3,依次为初始化调用次数、整次运行的调用次数、单次询问调用次数的最大值。只统计 MR 和 MC。grader.o 可用于检查操作是否合法和估测用时。checker.o 也会检查每次返回的边集合。提交程序应遵循函数接口,避免依赖具体的 info 内部表示。

样例

以下四组输入来自原赛附件,输出为 Hydro 版按各组输入应返回的校验值。

评分方式

只提交自己的 C++ 源码。

  • 未初始化的 info 类型的变量不保证是 emptyinfo。
  • 请不要尝试访问或修改 info 类型的成员变量,否则将被视为攻击交互库。
  • 请不要在 init 函数调用之前调用 MR 和 MC 函数,否则可能会发生未定义行为。
  • 你只能访问自己定义的变量和交互库返回的 info 类型变量,尝试访问其他空间将可能导致编译错误或运行时错误。

本题首先会受到和传统题相同的限制,例如编译错误会导致整道题目得 0 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。

在上述条件以外,在一个测试点中,若程序执行了非法的函数调用或询问操作中给出了错误回答,该测试点将会获得 0 分。否则,记 C1,C3C_1, C_3 分别表示你的程序在 init 函数中调用交互库函数的次数,和你的程序在所有 qq 次 ask 函数中调用交互库函数的次数的最大值。如果 C1≤3⋅107C_1 \le 3 \cdot {10}^7 且 C3C_3 不超过该测试点的评分参数 MM,你将获得该测试点的分数,否则你无法获得该测试点的分数。注意:计算 C1,C3C_1, C_3 时只会计入 MR、MC 函数的调用次数,而不会计入 isempty 函数的调用次数。

数据范围与提示

对于所有测试点,1≤n≤2×1051 \le n \le 2 \times {10}^5,1≤q≤1061 \le q \le {10}^6;每组询问中,有 1≤u≤n1 \le u \le n,1≤d≤n−11 \le d \le n - 1。

测试点 n=n= q=q= 特殊性质 M=M=
11 10001000 10410^4 500500
22 20002000
3,43,4 10510^5 10610^6 A 55
5,65,6 6×1046 \times 10^4 6×1046\times 10^4 B 5050
77 6×1046 \times 10^4 55
88 10510^5
99 75007500 5×1045 \times 10^4 C 500500
1010 10410^4
1111 1.5×1041.5 \times 10^4
1212 2×1042 \times 10^4 5050
1313 2.5×1042.5 \times 10^4 55
1414 3×1043 \times 10^4 10510^5
1515 6×1046 \times 10^4 10610^6 D
1616
1717 8×1048 \times 10^4
1818 10510^5
1919 1.5×1051.5 \times 10^5
2020 2×1052 \times 10^5 11

特殊性质 A:保证 ∀i∈[1,n−1]\forall i \in [1, n - 1],编号为 i+1i + 1 的点的父节点为 ii。
特殊性质 B:保证所有询问均满足 u=1u = 1。
特殊性质 C:保证所有询问均满足 d≤100d \le 100。
特殊性质 D:保证所有询问均满足 d≥1000d \ge 1000。

原题面 PDF