Description
风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。
很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 个地方，编号为
到
，被
条带权的边连接起来。每个地方都住着一个妖怪，其中第
个地方的妖怪年龄是
。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于
。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的
岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方
（
为编号），然后在
开一家面向年龄在
到
之间（即年龄大于等于
、小于等于
）的妖怪的店。也有可能
这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在
到
之间的妖怪，到点
的距离的和是多少（妖怪到
的距离是该妖怪所在地方到
的路径上的边的权之和） ，幽香把这个称为这个开店方案的方便值。
幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。
Input
第一行三个用空格分开的数 ，表示树的大小、开店的方案个数和妖怪的年龄上限。
第二行 个用空格分开的数
，
表示第
个地点妖怪的年龄，满足
。（年龄是可以为
的，例如刚出生的妖怪的年龄为
）
接下来 行，每行三个用空格分开的数
，表示树上的顶点
和
之间有一条权为
（
）的边，
和
是顶点编号。
接下来 行，每行三个用空格分开的数
。对于这
行的每一行，用
计算出
和
，表示询问“在地方
开店，面向妖怪的年龄区间为
的方案的方便值是多少”。对于其中第
行，
和
的计算方法为：
，
。对于第
到第
行，假设前一行得到的方便值为
，那么当前行的
和
计算方法为：
，
。
Output
对于每个方案，输出一行表示方便值。
Sample Input
10 10 10 0 0 7 2 1 4 7 7 7 9 1 2 270 2 3 217 1 4 326 2 5 361 4 6 116 3 7 38 1 8 800 6 9 210 7 10 278 8 9 8 2 8 0 9 3 1 8 0 8 4 2 7 9 7 3 4 7 0 2 2 7 3 2 1 2 3 4
Sample Output
1603 957 7161 9466 3232 5223 1879 1669 1282 0
HINT
对于所有数据，，
，
。
Solution
主席树
xjb维护一波。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<ll,ll>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2e5 + 66;
int n, m, A;
int v[N];
struct Edge {
int u, v, nxt, w;
}e[N * 2];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].w = z;
}
ll d[N];
int siz[N], son[N],fa[N], idw[N];
ll w[N];
void dfs1(int x, int F) {
siz[x] = 1;
fa[x] = F;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
// printf("%d->%d\n", x, y);
d[y] = d[x] + e[i].w;
idw[y] = e[i].w;
dfs1(y, x);
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
int top[N], num, id[N];
void dfs2(int x, int F) {
// printf("x=%d\n", x);
id[x] = ++num;
w[id[x]] = idw[x];
top[x] = F;
if(!son[x]) return;
dfs2(son[x], F);
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == son[x] || y == fa[x]) continue;
// printf("%d->%d\n", x, y);
dfs2(y, y);
}
}
int b[N], tot, r[N];
ll sum[N];
bool cmp(int x, int y) {
return v[x] < v[y];
}
int rt[N];
ll cnt[N];
struct T {
struct Tree {
int l, r;
ll s;
int tag;
}t[N * 35];
int tot;
void ins(int pre, int &o, int l, int r, int ql, int qr) {
o = ++tot;
t[o] = t[pre];
if(ql <= l && qr >= r) {
//t[o].s += w[r] - w[l - 1];
++t[o].tag;
return;
}
t[o].s += max(0ll, w[min(qr, r)] - w[max(l, ql) - 1]);
int mid = (l + r) >> 1;
if(ql <= mid) ins(t[pre].l, t[o].l, l, mid, ql, qr);
if(qr > mid) ins(t[pre].r, t[o].r, mid + 1, r, ql, qr);
//t[o].s = t[t[o].l].s + t[t[o].r].s;
//t[o].s += w[min(qr, r)] - w[max(l, ql) - 1];
}
ll query(int o, int l, int r, int ql, int qr,ll stag) {
if(!o) return 0;
ll res = (w[min(qr, r)] - w[max(l, ql) - 1]) * t[o].tag;
if(ql <= l && qr >= r) {
return t[o].s + res;
}
stag += t[o].tag;
int mid = (l + r) >> 1;
if(qr <= mid) return res + query(t[o].l, l, mid, ql, qr, stag);
if(ql > mid) return res + query(t[o].r, mid + 1, r, ql, qr, stag);
return res + query(t[o].l, l, mid, ql, qr, stag) + query(t[o].r, mid +1, r, ql, qr, stag);
}
}t;
void update(int &jd, int x) {
while(x) {
t.ins(jd, jd, 1, n, id[top[x]], id[x]);
x = fa[top[x]];
}
}
ll query(int pre, int o, int x) {
ll res = 0;
while(x) {
res += t.query(o, 1, n, id[top[x]], id[x], 0);
res -= t.query(pre, 1, n, id[top[x]], id[x], 0);
x = fa[top[x]];
}
return res;
}
ll solve(int u, int l, int r) {
ll ans = (cnt[r] - cnt[l - 1]) * d[u] + sum[r] - sum[l - 1];
// printf("sum1=%lld,sum2=%lld,sum3=%lld\n", (cnt[r] - cnt[l - 1]) * d[u], sum[r] - sum[l - 1], query(rt[l - 1], rt[r], u));
return ans - 2 * query(rt[l - 1], rt[r], u );
}
int main() {
// freopen("a.in","r",stdin);
n = read(), m = read(), A = read();
for(int i = 1; i <= n; ++i) b[++tot] = v[i] = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read(), z = read();
addedge(x, y, z);
addedge(y, x, z);
}
dfs1(1, 0);
dfs2(1, 1);
b[++tot] = -1;
sort(b +1, b +1 +tot);
tot = unique(b +1, b +1 + tot) - b - 1;
for(int i = 1; i <= n; ++i) v[i] = lower_bound(b +1, b +1 +tot, v[i]) - b;
for(int i = 1; i <= n; ++i) sum[v[i]] += d[i], w[i] += w[i - 1], ++cnt[v[i]];
for(int i = 1; i <= tot; ++i) sum[i] += sum[i - 1], cnt[i] += cnt[i - 1];
for(int i = 1; i <= n; ++i) r[i] = i;
sort(r +1, r +1 + n, cmp);
int p = 1;
for(int i = 1; i <= tot; ++i) {
rt[i] = rt[i - 1];
while(p <= n && v[r[p]] == i) update(rt[i], r[p]), ++p;
}
ll ans = 0;
for(int T = 1; T <= m; ++T) {
int u = read(), l = read(), r = read();
int x = l,y = r;
l = min((x + ans) % A, (y + ans) % A);
r = max((x + ans) % A, (y + ans) % A);
l = lower_bound(b + 1, b + 1 + tot, l) - b;
r = upper_bound(b + 1, b + 1 + tot, r) - b - 1;
// printf("u=%d,l=%d,r=%d %d\n",u, l,r, tot);
writeln(ans = solve(u, l, r));
}
return 0;
} 
京公网安备 11010502036488号