3786: 虚树(第一轮04)
题目描述
有一棵 n 个节点， 边权是正整数的树， 和一个 1 ~ n 的排列 p 。 有Q次询问， 每次给出 l, r, k，你需要回答在 p 的区间[l, r]中选 k 个点，问这 k 个点构成的虚树的边权和最大是 多少。sample.zip
inline void decode(int &l, int &r, int &k, i64 lstans, int testop) { lstans %= 19260817;
if(testop) {
l ^= lstans; l = (l % n + n) % n + 1; r ^= lstans; r = (r % n + n) % n + 1; if(l > r) std :: swap(l, r);
k ^= lstans;
k = (k % std :: min(r - l + 1, 100)) + 1; }
}
输入
第一行一个整数 id，表示测试点编号，样例编号为 0 。 第二行两个整数 op, n，表示是否 强制在线和树的大小。 接下来 n − 1 行，每行三个正整数 ui , vi , wi，表示ui , vi 之间有 一条边权为 wi 的边。 接下来一行 n 个数，表示排列 p。
接下来一行一个整数 Q，表示询问个数。 接下来 Q 行，每行三个正整数 l, r, k，含义如题。 若 op = 1，则当前测试点强制在线，每次的 l, r, k 需要调用下发的解码函数。
输出
输出包含若干行，对于每个询问输出一行一个正整数表示答案。
样例输入 复制
0
0 8
2 1 168841147
3 2 185715402
4 3 225620062
5 2 229186192
6 1 56387677
7 1 912381225
8 6 897978762
6 8 4 1 3 2 5 7
10
1 4 1
3 8 4
1 3 2
2 8 3
3 4 1
1 5 5
1 6 1
3 7 2
3 6 4
1 4 3样例输出 复制
0
1721744028
1534543050
2446924275
0
1534543050
0
640521656
580176611
1534543050提示
备注】
|
测试点编号 |
n |
Q |
k |
op |
特殊性质 |
|
1 |
8 |
10 |
8 |
0 |
无 |
|
2 |
8 |
10 |
8 |
1 |
无 |
|
3 |
100 |
100 |
100 |
0 |
|
|
4 |
100 |
100 |
100 |
1 |
|
|
5 |
1000 |
10000 |
100 |
0 |
|
|
6 |
1000 |
10000 |
100 |
1 |
|
|
7 |
200000 |
1000 |
100 |
0 |
|
|
8 |
200000 |
1000 |
100 |
1 |
|
|
9 − 10 |
200000 |
10000 |
2 |
0 |
|
|
11 |
200000 |
10000 |
100 |
0 |
树形态随机 |
|
12 |
200000 |
10000 |
100 |
1 |
树形态随机 |
|
13 |
200000 |
10000 |
100 |
0 |
1 的度数为 n - 1 |
|
14 |
200000 |
10000 |
100 |
1 |
1 的度数为 n - 1 |
|
15 - 16 |
200000 |
10000 |
100 |
0 |
l = 1, r = n |
|
17 - 18 |
200000 |
10000 |
100 |
0 |
r - l + 1 ≤ 100 |
|
19 |
200000 |
10000 |
100 |
0 |
|
|
20 |
200000 |
10000 |
100 |
1 |
|