#P11524. [2024省队模拟]天天爱跑步plus

[2024省队模拟]天天爱跑步plus

题目描述

小 C 和小 F 同学认为跑步非常非常有趣,于是决定制作一款叫做《天天爱跑步plus》的游戏。《天天爱跑步plus》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一棵包含 nn 个结点和 n−1n-1 条带权边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达,两个节点间的距离定义为树上路径的边权和。树上结点编号为从 11 到 nn 的连续正整数。

游戏将会进行 mm 天,第 ii 个节点每天有 cnticnt_i 个玩家上线,每天将会有若干个打卡点,所有玩家上线后会向距离最近的打卡点跑去。作为小 C 和小 F 的好基♂友 TLC ,你需要实时统计出每一天所有玩家跑步的距离和,即本题强制在线。

输入格式

第一行一个整数 TT ,代表测试点编号 (样例编号为 00 ) 。

第二行有两个整数 n,mn,m ,代表树的结点数和游戏进行的天数。

接下来 n−1n-1 行每行有三个整数 x,y,wx,y,w ,代表结点 xx 与结点 yy 之间有一条边权为 ww 的边。

接下来一行有 nn 个整数 cnticnt_i ,代表第 ii 个结点每天上线的玩家数。

接下来 mm 行第 ii 行先有一个整数 numinum_i ,代表第 ii 天开放的打卡点个数,随后有 numinum_i 个整数 ti,j′t_{i,j}' 代表加密后的开放的打卡点编号。

每天给出的打卡点编号经过了加密,实际的打卡点编号 ti,j=ti,j′⊕(ansi−1mod  n)t_{i,j}=t_{i,j}'\oplus (ans_{i-1}\mod n) ,其中 ansi−1ans_{i-1} 代表第 i−1i-1 天的答案(初始时 ans0=0ans_0=0 )

输出格式

输出 mm 行,每行一个整数 ansians_i ,代表第 ii 天的答案。

输入输出样例

输入 #1

0
5 5
1 2 1
1 3 1
3 4 1
3 5 1
1 2 3 4 5 
2 3 4 
3 1 4 5 
1 3 
2 5 1 
2 1 0 

输出 #1

10
5
14
13
10

输入 #2/输出 #2

见下发样例的 sample_runplus2.in/sample_runplus2.out,该样例满足测试点 11 的限制。

输入 #3/输出 #3

见下发样例的 sample_runplus3.in/sample_runplus3.out,该样例满足测试点 2∼32\sim 3 的限制。

输入 #4/输出 #4

见下发样例的 sample_runplus4.in/sample_runplus4.out,该样例满足测试点 4∼64\sim 6 的限制。

输入 #5/输出 #5

见下发样例的 sample_runplus5.in/sample_runplus5.out,该样例满足测试点 7∼107\sim 10 的限制。

输入 #6/输出 #6

见下发样例的 sample_runplus6.in/sample_runplus6.out,该样例满足测试点 15∼2015\sim 20 的限制。

说明/提示

样例 #1 说明

输入 #1 解密后为

0
5 5
1 2 1
1 3 1
3 4 1
3 5 1
1 2 3 4 5 
2 3 4 
3 1 4 5 
1 3 
2 1 5 
2 2 3

在第一天中,11 距离 33 最近,贡献为 1×1=11\times 1=1 ;22 距离 33 最近,贡献为 2×2=42\times 2=4 ;33 距离 33 最近,贡献为 3×0=03\times 0=0 ;44 距离 44 最近,贡献为 4×0=04\times0=0 ;55 距离 33 最近,贡献为 5×1=55\times 1=5 。故答案为 1+4+0+0+5=101+4+0+0+5=10

数据范围

对于 100% 的数据,1≤n≤2e51\leq n\leq 2e5 ,1≤m≤1e51\leq m\leq 1e5 ,1≤Σnum≤6e51\leq \Sigma num\leq 6e5 ,0≤cnti≤1e30\leq cnt_i\leq 1e3 ,0≤wi≤1e30\leq w_i\leq 1e3 ,1≤ti,j≤n1\leq t_{i,j}\leq n

测试点编号 nn mm Σnum\Sigma num 特殊性质
11 ≤5e3\leq 5e3 ≤1e3\leq 1e3 ≤6e3\leq 6e3 无
2∼32\sim3 ≤6e5\leq 6e5
4∼64\sim 6 ≤2e5\leq 2e5 ≤1e5\leq 1e5 ∀i=2n\forall _{i=2}^n ii 与 i−1i-1 直接连边
7∼107\sim 10 wi=1w_i=1
11∼1411\sim 14 ≤5e4\leq 5e4 ≤3e4\leq 3e4 ≤2e5\leq 2e5 无
15∼2015\sim 20 ≤2e5\leq 2e5 ≤1e5\leq 1e5 ≤6e5\leq 6e5