主席树。
推下式子，发现点的深度和好算，lca深度和不好算。
lca深度之和有个套路：先给a到根路径+1，再算b到根的和。
如果可以离线，即LNOI的LCA。本题强制在线，可持久化。
由于区间修改，使用标记永久化。
注意修改要复制全，关于和的修改有些细节：
int xiugai(int i, int j, int l, int r, int L, int R) {
if (R <= l || r <= L) return i;
int rt = ++sl;
cl[rt] = cl[i]; cr[rt] = cr[i];
he[rt] = he[i]; ld[rt] = ld[i];
if (L <= l && r <= R) {
he[rt] += su[j];
ld[rt] = ld[i] + 1;
return rt;
}
int m = (l + r) >> 1;
he[rt] -= (he[cl[rt]] + he[cr[rt]]);
cl[rt] = xiugai(cl[rt], j << 1, l, m, L, R);
cr[rt] = xiugai(cr[rt], (j << 1) | 1, m, r, L, R);
he[rt] += (he[cl[rt]] + he[cr[rt]]);
return rt;
}
正常空间需要4倍mlogn：修改区间拆分2倍，上传2倍。应该跑不满。
然而本题是树剖，跑不满，所以开到(2.5*10^7)就行。
代码：
#include <stdio.h>
#include <stdlib.h>
#define M 20000010
#define ll long long
#define re register
inline int max(int a, int b) {
return a > b ? a: b;
}
inline int min(int a, int b) {
return a < b ? a: b;
}
inline int read() {
re char ch;
while ((ch = getchar()) == '
' || ch == ' ' || ch == '
');
re int jg = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') jg = (jg << 3) + (jg << 1) + ch - '0';
return jg;
}
int fr[150010],ne[300010],v[300010],w[300010],bs = 0;
void addb(int a, int b, int c) {
v[bs] = b;
w[bs] = c;
ne[bs] = fr[a];
fr[a] = bs++;
}
int fa[150010],son[150010],sd[150010],cd[150010],jl[150010];
int dfs1(int u, int f) {
fa[u] = f;
sd[u] = sd[f] + 1;
jl[u] = jl[f] + cd[u];
int ma = -1,he = 1;
son[u] = -1;
for (int i = fr[u]; i != -1; i = ne[i]) {
if (v[i] == f) continue;
cd[v[i]] = w[i];
int rt = dfs1(v[i], u);
he += rt;
if (rt > ma) {
ma = rt;
son[u] = v[i];
}
}
return he;
}
int top[150010],bh[150010],tm = 0;
void dfs2(int u, int f, int tp) {
top[u] = tp;
bh[u] = ++tm;
if (son[u] == -1) return;
dfs2(son[u], u, tp);
for (int i = fr[u]; i != -1; i = ne[i]) {
if (v[i] != f && v[i] != son[u]) dfs2(v[i], u, v[i]);
}
}
int js[150010],cl[M],cr[M],ld[M],sl = 0,su[600010];
ll he[M],jh[150010];
void jianshu(int i, int l, int r) {
if (l + 1 == r) {
su[i] = js[l];
return;
}
int m = (l + r) >> 1;
jianshu(i << 1, l, m);
jianshu((i << 1) | 1, m, r);
su[i] = su[i << 1] + su[(i << 1) | 1];
}
int jianshu(int l, int r) {
int rt = ++sl;
he[rt] = ld[rt] = 0;
if (l + 1 == r) return rt;
int m = (l + r) >> 1;
cl[rt] = jianshu(l, m);
cr[rt] = jianshu(m, r);
return rt;
}
int build(int n) {
for (int i = 1; i <= n; i++) js[bh[i]] = cd[i];
jianshu(1, 1, n + 1);
return jianshu(1, n + 1);
}
int xiugai(int i, int j, int l, int r, int L, int R) {
if (R <= l || r <= L) return i;
int rt = ++sl;
cl[rt] = cl[i]; cr[rt] = cr[i];
he[rt] = he[i]; ld[rt] = ld[i];
if (L <= l && r <= R) {
he[rt] += su[j];
ld[rt] = ld[i] + 1;
return rt;
}
int m = (l + r) >> 1;
he[rt] -= (he[cl[rt]] + he[cr[rt]]);
cl[rt] = xiugai(cl[rt], j << 1, l, m, L, R);
cr[rt] = xiugai(cr[rt], (j << 1) | 1, m, r, L, R);
he[rt] += (he[cl[rt]] + he[cr[rt]]);
return rt;
}
ll getsum(int i, int j, int l, int r, int L, int R, int lh) {
if (R <= l || r <= L) return 0;
if (L <= l && r <= R) return 1ll * lh * su[j] + he[i];
int m = (l + r) >> 1;
return getsum(cl[i], j << 1, l, m, L, R, lh + ld[i]) + getsum(cr[i], (j << 1) | 1, m, r, L, R, lh + ld[i]);
}
int xiugai(int od, int x, int n) {
while (x != 0) {
od = xiugai(od, 1, 1, n + 1, bh[top[x]], bh[x] + 1);
x = fa[top[x]];
}
return od;
}
ll getsum(int ro, int x, int n) {
ll jg = 0;
while (x != 0) {
jg += getsum(ro, 1, 1, n + 1, bh[top[x]], bh[x] + 1, 0);
x = fa[top[x]];
}
return jg;
}
struct SPx {
int z, i;
};
SPx px[150010];
int cmp(const void * a, const void * b) {
return ((SPx * ) a) ->z - ((SPx * ) b) ->z;
}
int find(int n, int x) {
int l = 0, r = n;
while (l < r) {
int m = (l + r + 1) >> 1;
if (px[m].z <= x) l = m;
else r = m - 1;
}
return l;
}
int gen[150010];
ll getans(int L, int R, int u, int n) {
int r = find(n, R);
int l = find(n, L - 1);
ll lc = getsum(gen[r], u, n) - getsum(gen[l], u, n);
ll jg = 1ll * (r - l) * jl[u] + (jh[r] - jh[l]) - lc * 2;
return jg;
}
void insert(int i, int n) {
gen[i] = xiugai(gen[i - 1], px[i].i, n);
jh[i] = jh[i - 1] + jl[px[i].i];
}
int main() {
int n, q, m;
ll la = 0;
scanf("%d%d%d", &n, &q, &m);
for (int i = 1; i <= n; i++) {
fr[i] = -1;
px[i].i = i;
px[i].z = read();
}
qsort(px + 1, n, sizeof(SPx), cmp);
for (int i = 0; i < n - 1; i++) {
int a, b, c;
a = read();
b = read();
c = read();
addb(a, b, c);
addb(b, a, c);
}
dfs1(1, 0);
dfs2(1, 0, 1);
gen[0] = build(n);
for (int i = 1; i <= n; i++) insert(i, n);
for (int i = 0; i < q; i++) {
int u, a, b;
u = read();
a = read();
b = read();
int L = min((a + la) % m, (b + la) % m);
int R = max((a + la) % m, (b + la) % m);
la = getans(L, R, u, n);
printf("%lld
", la);
}
return 0;
}