You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

下发文件

题目描述

给定一颗 $n$ 个点的树。

$q$ 次查询只保留 $[l,r]$ 内的点，要求刻画出所有极大连通块。

具体的刻画要求是，若连通块为 $S_1,S_2,\cdots,S_k$，要求输出 $\sum_{i=1}^kf(S_i)\mod 2^{32}$。

我们提供了一个结构体用于维护集合，仅支持向其中加入一个点，以及查询 $f(S)$（$S$ 为当前集合）。

【实现细节】

请确保你的程序开头有如下一段代码。

struct component
{
	unsigned v;
};
const component emptycomponent=component{0};
void add(component&x,unsigned a);
unsigned val(component&x);

这段代码中定义了如下内容：

1. 定义了集合的数据类型 component。

2. 定义了空集所对应的 component 类型常量 emptycomponent，你可以在程序中直接使用。

3. 定义了以下修改函数，你可以在程序中直接调用：

   void add(component&x,unsigned a);
   

   • 这个函数表示向集合 $x$ 中加入点 $a$，你应当保证 $1\le a\le n$ 且不会加入已存在的点，否则该集合的 $f$ 值是无意义的。

4. 定义了函数 $f$，你可以在程序中直接调用：

   unsigned val(component&x);
   

   • 返回 $f(x)$。

你不需要，也不应该实现主函数。 你需要实现如下一个函数：

vector<unsigned> solve(int T,int n,int q,vector<int> u,vector<int> v,vector<int> l,vector<int> r);

• T 表示子任务编号，n 表示树的点数，q 表示询问数。
• u 和 v 的长度均为 $n-1$。对于 $0\le i<n-1$，$1\le u[i]<v[i]\le n$ 表示第 $i+1$ 条边的两个端点。
• l 和 r 的长度均为 $q$。对于 $0\le i<q$，$1\le l[i]\le r[i]\le n$ 表示第 $i+1$ 个询问。

你需要返回一个长度为 $q$ 的 vector，其中第 $i$ 项表示第 $i+1$ 个询问的答案。

测试时，在每个测试点，交互库会恰好调用一次 solve 函数。交互库会使用特殊的实现方式，单个 component 类型的变量会恒定消耗 $4$ 字节内存。

保证在满足调用次数限制且不进行 val 函数调用的情况下，交互库运行所需的时间不超过 0.5 秒，交互库本身所消耗的内存不超过 16 MiB。保证在只执行 $2\times 10^8$ 次 val 函数调用的情况下，交互库运行的时间不超过 0.5 秒。

【测试程序方式】

本题目录下提供了交互库的参考实现 sample_grader.cpp。最终测试时所用的交互库实现与该实现有不同，因此选手的解法不应依赖交互库的具体实现，同时也不应该依赖其中 add 函数和 val 函数的具体实现。

选手可以在使用如下命令编译得到可执行程序（假设选手程序命名为 code.cpp）：

g++ code.cpp sample_grader.cpp -o code -O2 -std=c++14 -lm

按上述方法编译得到的可执行文件 code，其运行方式如下：

• 可执行文件将从标准输入读入以下格式的数据：
  • 第一行三个整数 $T, n, q$，分别表示子任务编号、树的点数、询问数；
  • 接下来 $n-1$ 行每行两个整数 $u, v$，描述一条边。
  • 接下来 $q$ 行每行两个整数 $l, r$，描述一次询问。
• 读入之后，交互库会进行测试。如果你的程序不满足交互库限制，其会在输出中返回对应的错误信息。否则，对于链接的可执行文件，其输出如下：
  • 一行 $q$ 个整数，表示你的程序对于每个询问给出的答案，可以与对应的答案文件进行比较检查正确性。
  • 一行一个整数，表示你的程序调用 add 函数的总次数。

输入格式

见【测试程序方式】。

输出格式

见【测试程序方式】。

说明/提示

【样例 #1】

见附件中的 sample1.in 与 sample1.out。

该样例数据范围不满足任何一个子任务，因此其子任务编号为 $0$。

【样例 #2】

见附件中的 sample2.in 与 sample2.out。

该样例满足子任务 4 的数据范围，因此其子任务编号为 $4$。

在一个测试点，你的程序至多能调用 $1.3\times 10^8$ 次 add 函数，val 函数的调用次数不限。

【数据范围】

对于所有测试点，$1\le n,q\le 10^5$。

特殊性质 A：保证第 $i$ 条边连接 $i$ 和 $i+1$。
特殊性质 B：保证树在所有可能的形态中等概率随机生成。
特殊性质 C：保证每个点的度数 $\le2$。