【题目描述】

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

样例下载：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$, $𝑛$，表示是否 强制在线和树的大小。

接下来 $𝑛 − 1$ 行，每行三个正整数 $𝑢_𝑖$ , $𝑣_𝑖$ , $𝑤_𝑖$，表示 $𝑢_𝑖$ , $𝑣_𝑖$ 之间有一条边权为 $𝑤_𝑖$ 的边。 接下来一行 $𝑛$ 个数，表示排列 $𝑝$。

接下来一行一个整数 $𝑄$，表示询问个数。

接下来 $𝑄$ 行，每行三个正整数 $𝑙, 𝑟, 𝑘$，含义如题。

若 $op = 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

【备注】