#2032. 《关于因为与去年互测zjk撞题而不得不改题这回事》
《关于因为与去年互测zjk撞题而不得不改题这回事》
《关于因为与去年互测zjk撞题而不得不改题这回事》
题目描述
标题: 《关于因为与去年互测zjk撞题而不得不改题这回事》 - Problem - QOJ.ac
#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》
The problem was used in the following contests:
题目背景
shik 吞进去又吐出来。ber♂宇和抵德纠缠个不清。天空中的素数还没有降下。
你站在椭圆的一♂焦,伟大尼特向你发问。
题目描述
尼特问的这个问题是这样的,首先你有一棵 n 个节点的树,节点标号 1∼n,树上每个节点都有一个权值 vi。
然后尼特会询问 Q 次,每次询问树上的两个节点 x,y,以及一个数 m。
然后你需要返回在这两个节点形成的简单路径上选取 m 个节点,并将其权值按位与起来获得的值最大是多少。
特别的,如果这条路径上的节点不足 m 个,你要返回 0。
由于 shik,尼特的询问强制在线。
输入格式
第一行单独的一个数 n,表示节点个数 n。
接下来 n−1 行,每行有两个空格隔开的整数 x,y,表示节点 x,y 之间有一条边。
再接下来单独一行 n 个非负整数 vi,表示每个节点的权值,其中第 i 个非负整数 vi 表示第 i 个节点的权值。
接下来一行单独的一个整数 Q,表示询问个数。
接下来 Q 行,每行三个整数 x,y,m,由于强制在线,你需要解密得到真正的x,y,不妨设上一次你输出的答案为 lastans(第一次询问 lastans 视作 0),则真正的 x′,y′ 可以使用以下方式获取:
x′=((x⊕lastans)modn)+1,y′=((y⊕lastans)modn)+1,其中 ⊕ 代表按位异或。
输出格式
Q 行,每行一个非负整数代表你的答案
样例数据
样例输入一
5
1 2
3 1
4 3
5 4
274 5134 2066 17120 40972
3
4 4 2
3 1 2
1 4 2
样例输出一
0
18
0
样例解释一
在这组数据中树是一条链。
解密得到三组询问的 (x,y) 分别是 (5,5),(4,2) 和 (5,3)。
其中第一个询问路径上不满两个数,从而为 0。
对于第二个询问,其经过 1,2,3,4 节点,通过选取 1,3,我们得到 274and2066=18 最大。
对于第三个询问,其经过 3,4,5,容易验算选取三对的答案都是 0。
样例输入二
10
2 1
3 1
4 1
5 2
6 1
7 1
8 7
9 3
10 3
53290 0 388 0 70 2 9750 2114 186 0
3
6 5 3
5 8 3
3 1 3
样例输出二
2
2
0
样例解释二
这是随机树的数据,解密得到 (7,6),(8,1),(2,4)
限制与约定
子任务 分值 n⩽ m⩽ Q⩽ V⩽ 特殊性质 1 5 103 3 1 树是一条链 2 5 105 3 10 105 2 1 65535 4 5 106 5 10 105 104 6 15 7 15 106 105 树按照某种方式随机生成 8 35
其中 V 表示权值范围,如表格中无特殊说明(即空白),则有 n⩽106,m 在 [2,10] 之间随机生成,Q⩽105,0⩽vi⩽262−1,树为普通的树。
树按照某种随机方式生成的意思是,对于第 i 个点,2⩽i⩽n,有 i 向 [1,i−1] 中均匀随机的一个数连边。
对于题目中询问的 x,y(加密前),保证有 1⩽x,y⩽n。
提示
读入量偏大,请使用比较高效的读入方式
keep your determinant!
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5
1 2
3 1
4 3
5 4
274 5134 2066 17120 40972
3
4 4 2
3 1 2
1 4 2
0
18
0
样例 2
10
2 1
3 1
4 1
5 2
6 1
7 1
8 7
9 3
10 3
53290 0 388 0 70 2 9750 2114 186 0
3
6 5 3
5 8 3
3 1 3
2
2
0