{"problem":{"name":"『GROI-R1』 湖底之城","description":{"content":"悦，玲和荧三个人在湖底之城闲游。湖底之城的道路错综复杂，形成了一棵有 $n$ 个节点的树。 她们三人的手上都有一个计数器，初始都为 $0$。她们每走到一个点的时候，**悦和荧**手上的计数器会自动加上刚刚经过的**这条边的边权**，同时**玲**的计数器会恰好**增加 $1$**。同时，她们整个过程中**没有经过某个点超过一次**。 由于她们的计数器不能存储很大的值，所以，当**玲**的计数器","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8975"},"statements":[{"statement_type":"Markdown","content":"悦，玲和荧三个人在湖底之城闲游。湖底之城的道路错综复杂，形成了一棵有 $n$ 个节点的树。\n\n她们三人的手上都有一个计数器，初始都为 $0$。她们每走到一个点的时候，**悦和荧**手上的计数器会自动加上刚刚经过的**这条边的边权**，同时**玲**的计数器会恰好**增加 $1$**。同时，她们整个过程中**没有经过某个点超过一次**。\n\n由于她们的计数器不能存储很大的值，所以，当**玲**的计数器上的值是「湖之数」$p$ 的**倍数**时，**悦可以**将她的计数器上的值减去**荧**的计数器上的值，接下来，**玲和荧**的计数器都会立刻**归零**。\n\n玘现在不知道她们闲游的起点和终点，所以天生计算能力很好的玘对于每一对起点和终点，计算出了悦手上计数器在终点时可能出现的最小值。玘把这个值记作 $f(u,v)$，意思是她们从点 $u$ 走到了点 $v$。可是，玘认为，没有红色彼岸花的寒，一定是算不出来这些答案的。所以，他让寒做一道更简单的题。玘给寒一个长度为 $m$ 的序列 $s$，让寒对于每一个点为 $u$ 时计算 $\\min\\limits_{i=1}^m\\{f(s_i,u)\\}$。\n\n**形式化题面**\n\n给定一个 $n$ 个点的树 $(V,E)$ 和一个正整数 $p$，每一条边有一个整数边权 $w_i$。\n\n我们定义 $f(s,v)$ 表示为对 $u,a,b,c$ 进行若干次**拓展**后可以得到的当 $u=v$ 时的 $a$ 的最小值，其中最开始 $u\\gets s$ 同时 $a,b,c\\gets0$。\n\n**拓展**的定义为依次进行如下操作：\n\n- 选择任意一条边 $(u',v,w)\\in E$ 满足 $u=u'$，令 $u\\gets v,a\\gets a+w,b\\gets b+1,c\\gets c+w$；\n\n- 如果 $p\\mid b$，你****可以****令 $a\\gets a-c,b\\gets 0,c\\gets0$。\n\n特别地，对于每一次**拓展**，你**不能**取一个之前取过的点。\n\n给定序列 $\\{s_m\\}$，对于每个点 $u$ 求 $\\min\\limits_{i=1}^m\\{f(s_i,u)\\}$。\n\n## Input\n\n第一行三个整数 $n,m,p$，表示树的节点数为 $n$，编号分别为 $1\\sim n$，「湖之数」为 $p$，序列 $s$ 的长度为 $m$。\n\n接下来 $n-1$ 行每行三个整数 $u,v,w$ 表示存在一条连接 $u,v$ 两个点，边权为 $w$ 的边。\n\n接下来一行 $m$ 个整数表示 $s_{1\\sim m}$ 即 $m$ 个起点。\n\n## Output\n\n设 $ans_u=\\min\\limits_{i=1}^m\\{f(s_i,u)\\}$，那么你需要输出 $\\text{xor}_{i=1}^n |ans_i|$。其中 $|a|$ 表示 $a$ 的绝对值。\n\n[samples]\n\n## Background\n\n那年你我仍是无瑕的少年\n\n在夜晚安逸的后院无所顾忌地笑谈人生\n\n——怀念这样毫无猜忌的时光\n\n## Note\n\n**样例解释**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/xo9b4yyn.png)\n\n - 如果她们从 $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$。\n \n- 如果她们从 $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$。\n\n综上的 $\\{ans_n\\}=\\{-5,-3,-4,-3,-5,0\\}$。计算可得 $\\text{xor}_{i=1}^n |ans_i|=4$。\n\n**数据范围**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 数据范围 | 特殊性质 | 分值 |\n| :----------: | :----------: | :----------: | :----------: |\n| $\\text{Subtask1}$ | $m\\le n\\le100$，$p\\le20$ |  | $10$ |\n| $\\text{Subtask2}$ | $m\\le n\\le10^3$，$p\\le100$ |  | $15$ |\n| $\\text{Subtask3}$ | $n\\le10^5$，$p\\le100$，$m=1$ |  | $10$ |\n| $\\text{Subtask4}$ | $m\\le n\\le10^5$，$p=1$ |  | $20$ |\n| $\\text{Subtask5}$ | $m\\le n\\le10^5$，$p\\le100$ | 有 | $10$ |\n| $\\text{Subtask6}$ | $m\\le n\\le10^5$，$p\\le100$ |  | $35$ |\n\n特殊性质：保证树退化成一条链。\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8975","tags":["动态规划 DP","图论","O2优化","树形 DP"],"sample_group":[["6 2 2\n1 2 -2\n1 3 1\n1 4 2\n2 5 -3\n2 6 10\n1 5\n","4"]],"created_at":"2026-03-03 11:09:25"}}