『GROI-R1』 湖底之城

那年你我仍是无瑕的少年 在夜晚安逸的后院无所顾忌地笑谈人生 ——怀念这样毫无猜忌的时光

悦，玲和荧三个人在湖底之城闲游。湖底之城的道路错综复杂，形成了一棵有 $n$ 个节点的树。 她们三人的手上都有一个计数器，初始都为 $0$。她们每走到一个点的时候，**悦和荧**手上的计数器会自动加上刚刚经过的**这条边的边权**，同时**玲**的计数器会恰好**增加 $1$**。同时，她们整个过程中**没有经过某个点超过一次**。 由于她们的计数器不能存储很大的值，所以，当**玲**的计数器上的值是「湖之数」$p$ 的**倍数**时，**悦可以**将她的计数器上的值减去**荧**的计数器上的值，接下来，**玲和荧**的计数器都会立刻**归零**。 玘现在不知道她们闲游的起点和终点，所以天生计算能力很好的玘对于每一对起点和终点，计算出了悦手上计数器在终点时可能出现的最小值。玘把这个值记作 $f(u,v)$，意思是她们从点 $u$ 走到了点 $v$。可是，玘认为，没有红色彼岸花的寒，一定是算不出来这些答案的。所以，他让寒做一道更简单的题。玘给寒一个长度为 $m$ 的序列 $s$，让寒对于每一个点为 $u$ 时计算 $\min\limits_{i=1}^m\{f(s_i,u)\}$。 **形式化题面** 给定一个 $n$ 个点的树 $(V,E)$ 和一个正整数 $p$，每一条边有一个整数边权 $w_i$。 我们定义 $f(s,v)$ 表示为对 $u,a,b,c$ 进行若干次**拓展**后可以得到的当 $u=v$ 时的 $a$ 的最小值，其中最开始 $u\gets s$ 同时 $a,b,c\gets0$。 **拓展**的定义为依次进行如下操作： - 选择任意一条边 $(u',v,w)\in E$ 满足 $u=u'$，令 $u\gets v,a\gets a+w,b\gets b+1,c\gets c+w$； - 如果 $p\mid b$，你****可以****令 $a\gets a-c,b\gets 0,c\gets0$。 特别地，对于每一次**拓展**，你**不能**取一个之前取过的点。 给定序列 $\{s_m\}$，对于每个点 $u$ 求 $\min\limits_{i=1}^m\{f(s_i,u)\}$。

第一行三个整数 $n,m,p$，表示树的节点数为 $n$，编号分别为 $1\sim n$，「湖之数」为 $p$，序列 $s$ 的长度为 $m$。 接下来 $n-1$ 行每行三个整数 $u,v,w$ 表示存在一条连接 $u,v$ 两个点，边权为 $w$ 的边。 接下来一行 $m$ 个整数表示 $s_{1\sim m}$ 即 $m$ 个起点。

设 $ans_u=\min\limits_{i=1}^m\{f(s_i,u)\}$，那么你需要输出 $\text{xor}_{i=1}^n |ans_i|$。其中 $|a|$ 表示 $a$ 的绝对值。

6 2 2
1 2 -2
1 3 1
1 4 2
2 5 -3
2 6 10
1 5

4

**样例解释**  - 如果她们从 $1$ 号点出发，首先有 $f(1,1)=0$。走到点 $2,3,4$ 时悦的计数器上的值分别为 $-2,1,2$，所以 $f(1,2)=-2,f(1,3)=1,f(1,4)=2$。她们走到点 $5,6$ 时，悦的计数器上的值分别为 $-5,8$。由于这时玲的计数器上的值等于 $2$，是 $p$ 的倍数，所以悦**可以**选择让她手上的计数器的值减去荧的计数器的值，不难得出 $f(1,5)=-5,f(1,6)=0$。 - 如果她们从 $5$ 号点出发，同理可得 $f(5,5)=0,f(5,2)=-3,f(5,6)=0,f(5,1)=-5,f(5,4)=-3,f(5,3)=-4$。 综上的 $\{ans_n\}=\{-5,-3,-4,-3,-5,0\}$。计算可得 $\text{xor}_{i=1}^n |ans_i|=4$。 **数据范围** **本题采用捆绑测试。** | 子任务编号 | 数据范围 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | | $\text{Subtask1}$ | $m\le n\le100$，$p\le20$ | | $10$ | | $\text{Subtask2}$ | $m\le n\le10^3$，$p\le100$ | | $15$ | | $\text{Subtask3}$ | $n\le10^5$，$p\le100$，$m=1$ | | $10$ | | $\text{Subtask4}$ | $m\le n\le10^5$，$p=1$ | | $20$ | | $\text{Subtask5}$ | $m\le n\le10^5$，$p\le100$ | 有 | $10$ | | $\text{Subtask6}$ | $m\le n\le10^5$，$p\le100$ | | $35$ | 特殊性质：保证树退化成一条链。 对于 $100\%$ 的数据 $1\le m\le n\le10^5$，$1\le p\le100$，$-10^4\le w\le10^4$，$1\le u,v,s_i\le n$。