QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》

Statistics

时间限制 $\texttt{3s}$

空间限制 $\texttt{512MB}$

题目背景

shik 吞进去又吐出来。ber♂宇和抵德纠缠个不清。天空中的素数还没有降下。

你站在椭圆的一♂焦,伟大尼特向你发问。

题目描述

尼特问的这个问题是这样的,首先你有一棵 $n$ 个节点的树,节点标号 $1∼n$,树上每个节点都有一个权值 $v_i$。

然后尼特会询问 $Q$ 次,每次询问树上的两个节点 $x,y$,以及一个数 $m$。

然后你需要返回在这两个节点形成的简单路径上选取 $m$ 个节点,并将其权值按位与起来获得的值最大是多少。

特别的,如果这条路径上的节点不足 $m$ 个,你要返回 $0$。

由于 shik,尼特的询问强制在线。

输入格式

第一行单独的一个数 $n$,表示节点个数 $n$。

接下来 $n−1$ 行,每行有两个空格隔开的整数 $x,y$,表示节点 $x,y$ 之间有一条边。

再接下来单独一行 $n$ 个非负整数 $v_i$,表示每个节点的权值,其中第 $i$ 个非负整数 $v_i$ 表示第 $i$ 个节点的权值。

接下来一行单独的一个整数 $Q$,表示询问个数。

接下来 $Q$ 行,每行三个整数 $x,y,m$,由于强制在线,你需要解密得到真正的$x,y$,不妨设上一次你输出的答案为 $lastans$(第一次询问 $lastans$ 视作 $0$),则真正的 $x',y'$ 可以使用以下方式获取:

$x'=((x⊕lastans)\bmod n)+1$,$y'=((y⊕lastans)\bmod n)+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$,我们得到 $274 \operatorname{and} 2066=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\leqslant$ $m\leqslant$ $Q\leqslant$ $V\leqslant$ 特殊性质
$1$ $5$ $10^3$ $3$ $1$ $ $ 树是一条链
$2$ $5$ $10^5$
$3$ $10$ $10^5$ $2$ $1$ $65535$
$4$ $5$ $10^6$ $ $ $ $
$5$ $10$ $10^5$ $10^4$
$6$ $15$ $ $
$7$ $15$ $10^6$ $10^5$ 树按照某种方式随机生成
$8$ $35$ $ $

其中 $V$ 表示权值范围,如表格中无特殊说明(即空白),则有 $n⩽10^6$,$m$ 在 $[2,10]$ 之间随机生成,$Q⩽10^5$,$0⩽v_i⩽2^{62}−1$,树为普通的树。

树按照某种随机方式生成的意思是,对于第 $i$ 个点,$2⩽i⩽n$,有 $i$ 向 $[1,i−1]$ 中均匀随机的一个数连边。

对于题目中询问的 $x,y$(加密前),保证有 $1⩽x,y⩽n$。

提示

读入量偏大,请使用比较高效的读入方式

keep your determinant!