#PQJ1434x7855. QOJ 1434_7855

    ID: 2607 传统题 5000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测树上算法

QOJ 1434_7855

标题: 不跳棋 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

给一棵有 n 个节点的树,初始每个节点上都有一个棋子。

共有 n−2 次操作,每次拿走树上的一个棋子。

请在每次操作后输出最小的任意两个不同棋子的树上距离以及最小距离的点对数量,询问部分强制在线。

输入格式

第一行两个整数 n,tp。

接下来 n−1 行每行两个整数 u,v 表示树边 (u,v)。

接下来 n−2 行每行一个整数 x′ 表示拿走 x=x′⊕(lastans×tp) 上的棋子,其中 ⊕ 表示异或操作。初始 lastans=0,之后表示上一次询问的点对数量。

输出格式

共 n−2 行,每行两个整数表示最短距离和点对数量。

样例 #1

样例输入 #1

5 0
1 2
2 3
3 4
4 5
2
4
3

样例输出 #1

1 2
2 2
4 1

样例 #2

样例输入 #2

10 1
1 2
1 3
3 4
4 5
5 6
3 7
1 8
6 9
9 10
6
2
1
4
8
2
9
11

样例输出 #2

1 7
1 6
1 5
1 2
1 1
2 1
3 2
3 1

数据范围及约束

对于 100% 的数据,2≤n≤5×105,1≤u,v,x≤n,x 不重复。

测试点n≤tp=其它限制1∼31000无4∼610000无7∼122×1050无13∼162×1051u+1=v17∼202×1051无21∼255×1051无