You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

有一棵 $𝑛$ 个节点，边权是正整数的树，和一个 $1 ∼ 𝑛$ 的排列 $𝑝$。 有$𝑄$次询问，每次给出$𝑙$, $𝑟$, $𝑘$，你需要回答在 $𝑝$ 的区间$[𝑙, 𝑟]$中选 $𝑘$ 个点，问这 $𝑘$ 个点构成的虚树的边权和最大是多少。

inline void decode(int &l, int &r, int &k, i64lstans, 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;
    }
}

【输入格式】

第一行一个整数 $𝑖𝑑$，表示测试点编号，样例编号为 0。 第二行两个整数 $𝑜𝑝$, $𝑛$，表示是否强制在线和树的大小。 接下来 $𝑛 − 1$ 行，每行三个正整数 $𝑢_𝑖$ , $𝑣_𝑖$ , $𝑤_𝑖$，表示$𝑢_𝑖$ , $𝑣_𝑖$ 之间有一条边权为 $𝑤_𝑖$ 的边。 接下来一行 $𝑛$ 个数，表示排列 $𝑝$。 接下来一行一个整数 $𝑄$，表示询问个数。 接下来 $𝑄$ 行，每行三个正整数 $𝑙$, $𝑟$, $𝑘$，含义如题。 若 $𝑜𝑝 = 1$，则当前测试点强制在线，每次的 $𝑙$, $𝑟$, $𝑘$ 需要调用下发的解码函数。

【输出格式】

输出包含若干行，对于每个询问输出一行一个正整数表示答案。

【样例 1 输入】

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

【样例 1 输出】

0
1721744028
1534543050
2446924275
0
1534543050
0
640521656
580176611
1534543050