P8975 "GROI-R1" City at the Bottom of the Lake

That year, you and I were still flawless teenagers. In the quiet backyard at night, we laughed and talked about life without any worries. — Missing those days with no suspicion at all.

Yue, Ling, and Ying are wandering in the City at the Bottom of the Lake. The roads there are complicated and form a tree with $n$ nodes. Each of them has a counter, all starting at $0$. Whenever they arrive at a node, **Yue and Ying**’s counters will automatically increase by the **weight of the edge they just walked through**, while **Ling**’s counter will increase by **exactly $1$**. Also, during the whole process, they **never pass through any node more than once**. Because their counters cannot store very large values, when **Ling**’s counter is a **multiple** of the “Lake Number” $p$, **Yue may** subtract the value of **Ying**’s counter from her own counter, and then **Ling and Ying**’s counters will both be **reset to zero immediately**. Qi does not know their starting point and ending point, so for every pair of start and end nodes, the naturally strong-at-calculation Qi computed the minimum possible value that could appear on Yue’s counter at the ending node. Qi denotes this value as $f(u,v)$, meaning they walked from node $u$ to node $v$. However, Qi believes that without the red spider lily, Han surely cannot compute these answers. So he asks Han to solve an easier problem. Qi gives Han a sequence $s$ of length $m$, and asks Han to compute $\min\limits_{i=1}^m\{f(s_i,u)\}$ for every node $u$. **Formal Statement** Given a tree $(V,E)$ with $n$ nodes and a positive integer $p$. Each edge has an integer weight $w_i$. We define $f(s,v)$ as the minimum value of $a$ when $u=v$ that can be obtained after performing the operation **extension** several times on $u,a,b,c$, where initially $u\gets s$ and $a,b,c\gets0$. An **extension** is defined as performing the following operations in order: - Choose any edge $(u',v,w)\in E$ such that $u=u'$, then set $u\gets v,a\gets a+w,b\gets b+1,c\gets c+w$; - If $p\mid b$, you **may** set $a\gets a-c,b\gets 0,c\gets0$. In particular, in each **extension**, you **cannot** choose a node that has been chosen before. Given the sequence $\{s_m\}$, for every node $u$, find $\min\limits_{i=1}^m\{f(s_i,u)\}$.

The first line contains three integers $n,m,p$, meaning the tree has $n$ nodes labeled $1\sim n$, the “Lake Number” is $p$, and the length of sequence $s$ is $m$. The next $n-1$ lines each contain three integers $u,v,w$, meaning there is an edge connecting nodes $u$ and $v$ with weight $w$. The next line contains $m$ integers representing $s_{1\sim m}$, i.e. the $m$ starting nodes.

Let $ans_u=\min\limits_{i=1}^m\{f(s_i,u)\}$. You need to output $\text{xor}_{i=1}^n |ans_i|$, where $|a|$ denotes the absolute value of $a$.

**Sample Explanation**  - If they start from node $1$, first we have $f(1,1)=0$. When they walk to nodes $2,3,4$, the values on Yue’s counter are $-2,1,2$ respectively, so $f(1,2)=-2,f(1,3)=1,f(1,4)=2$. When they walk to nodes $5,6$, the values on Yue’s counter are $-5,8$ respectively. Since Ling’s counter is $2$ at this time, which is a multiple of $p$, Yue **may** choose to subtract Ying’s counter from her counter. It is not hard to get $f(1,5)=-5,f(1,6)=0$. - If they start from node $5$, similarly we can get $f(5,5)=0,f(5,2)=-3,f(5,6)=0,f(5,1)=-5,f(5,4)=-3,f(5,3)=-4$. Therefore, $\{ans_n\}=\{-5,-3,-4,-3,-5,0\}$. We can compute that $\text{xor}_{i=1}^n |ans_i|=4$. **Constraints** **This problem uses bundled testdata.** | Subtask ID | Constraints | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | | $\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$ | Yes | $10$ | | $\text{Subtask6}$ | $m\le n\le10^5$，$p\le100$ | | $35$ | Special property: it is guaranteed that the tree degenerates into a chain. For $100\%$ of the data, $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$. Translated by ChatGPT 5