妈的，杀软动态点分治。
你考虑建出点分树，然后把所有子树塞进该点。
根据经典结论 \(\sum dep_x = \sum sz_x = n\log n\) 然后我们考虑每次按照 \(v\) 来排序，做前缀和，然后我们发现每次我们只需要查询一段区间和，使用二分查找即可。
注意容斥，具体来说，就是考虑在 \(x\) 的时候容斥掉 \(sub_x \to fa_x\) 这一类的贡献，可以在建树的时候计算 \(dis_{t \to fa_x}\) 即可，然后我们用子树大小减去不合法的再乘上 \(dis_{x \to fa_{pos}}\) 即可。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
using namespace std;
typedef long long ll;
const int _ = 2e5 + 5, mod = 998244353, inf = 0x3f3f3f3f;
int power (int x, int y) {
int ret = 1;
for ( ; y; y >>= 1, x = 1ll * x * x % mod)
if (y & 1) ret = 1ll * ret * x % mod;
return ret;
}
void add (int & x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
int mul (int x, int y) { return 1ll * x * y % mod; }
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
using namespace std;
typedef long long ll;
const int _ = 2e5 + 5, mod = 998244353, inf = 0x3f3f3f3f;
int power (int x, int y) {
int ret = 1;
for ( ; y; y >>= 1, x = 1ll * x * x % mod)
if (y & 1) ret = 1ll * ret * x % mod;
return ret;
}
void add (int & x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
int mul (int x, int y) { return 1ll * x * y % mod; }
int n, q, A, mxs, all, rt, fa[_];
int a[_];
int sz[_], dis[_], dep[_], son[_], top[_], pa[_];
bool vis[_];
ll lst;
struct Info {
int v;
ll s;
bool operator < (const Info & x) const { return v < x. v; }
} ;
vector <pair<int, int> > e[_];
vector <Info> v[2][_];
void dfs1 (int x, int fa) {
sz[x] = 1;
pa[x] = fa, dep[x] = dep[fa] + 1;
for (auto & [y, w] : e[x]) {
if (y == fa) continue ;
dis[y] = dis[x] + w;
dfs1(y, x), sz[x] += sz[y];
if (sz[y] > sz[son[x]]) son[x] = y;
}
}
void dfs2 (int x, int anc) {
top[x] = anc;
if (son[x]) dfs2(son[x], anc);
for (auto & [y, w] : e[x]) if (y ^ pa[x] && y ^ son[x]) dfs2(y, y);
}
int dist (int x, int y) {
int ret = dis[x] + dis[y], lc;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = pa[top[x]];
}
lc = dep[x] < dep[y] ? x : y;
return ret - dis[lc] * 2;
}
void getrt (int x, int anc) {
sz[x] = 1;
int ms = 0;
for (auto & [y, w] : e[x]) {
if (vis[y] || y == anc) continue ;
getrt(y, x), sz[x] += sz[y], ms = max(ms, sz[y]);
}
ms = max(all - sz[x], ms);
if (ms < mxs) rt = x, mxs = ms;
}
void dfs3 (int x, int anc, int d) {
sz[x] = 1;
v[0][rt].push_back({a[x], d});
if (fa[rt]) v[1][rt].push_back({a[x], dist(fa[rt], x)});
for (auto & [y, w] : e[x]) {
if (y == anc || vis[y]) continue ;
dfs3(y, x, d + w);
sz[x] += sz[y];
}
}
void build (int x) {
// cout << x << endl;
vis[x] = 1, dfs3(x, 0, 0);
for (auto & [y, w] : e[x]) {
if (vis[y]) continue ;
all = mxs = sz[y], rt = 0;
getrt(y, x), fa[rt] = x;
build(rt);
}
}
ll query (int op, int x, int l, int r, ll &len) {
int lp = lower_bound(v[op][x].begin(), v[op][x].end(), (Info){l, 0}) - v[op][x].begin() - 1,
rp = upper_bound(v[op][x].begin(), v[op][x].end(), (Info){r, 0}) - v[op][x].begin() - 1;
len = rp - lp;
ll ret = 0;
if (lp >= 0 && lp < v[op][x].size()) ret -= v[op][x][lp].s;
if (rp >= 0 && rp < v[op][x].size()) ret += v[op][x][rp].s;
return ret;
}
int main() {
/*
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
黛拉可玛莉·岗德森布莱德，一亿年一遇美少女。
*/
cin >> n >> q >> A;
rep(i, 1, n) scanf("%d", & a[i]);
rep(i, 1, n - 1) {
int x, y, z;
scanf("%d%d%d", & x, & y, & z);
e[x].push_back({y, z}), e[y].push_back({x, z});
}
dfs1(1, 0), dfs2(1, 1);
all = mxs = n, getrt(1, 0), build(rt);
rep(x, 1, n) {
sort(v[0][x].begin(), v[0][x].end()),
sort(v[1][x].begin(), v[1][x].end());
for (int j = 1; j < v[0][x].size(); j ++)
v[0][x][j].s += v[0][x][j - 1].s;
for (int j = 1; j < v[1][x].size(); j ++)
v[1][x][j].s += v[1][x][j - 1].s;
}
while (q --) {
int x, l, r;
ll p, q;
scanf("%d%lld%lld", & x, & p, & q);
l = min((p + lst) % A, (q + lst) % A),
r = max((p + lst) % A, (q + lst) % A);
ll t1, t2;
lst = query(0, x, l, r, t1);
for (int pos = x; fa[pos]; pos = fa[pos]) {
lst += query(0, fa[pos], l, r, t1) - query(1, pos, l, r, t2);
lst += (t1 - t2) * dist(fa[pos], x);
}
printf("%lld\n", lst);
}
return 0;
}
刘伟在知乎上被找到帐号不是很正常。