「BZOJ4012」[HNOI2015]开店

Description

风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。

很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 nn 个地方,编号为 11nn,被 n1n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 ii 个地方的妖怪年龄是 xix_i。妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 33。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 1818 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 uuuu 为编号),然后在 uu 开一家面向年龄在 LLRR 之间(即年龄大于等于 LL、小于等于 RR)的妖怪的店。也有可能 uu 这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 LLRR 之间的妖怪,到点 uu 的距离的和是多少(妖怪到 uu 的距离是该妖怪所在地方到 uu 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。

幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。

Input

第一行三个用空格分开的数 n,Q,An,Q,A,表示树的大小、开店的方案个数和妖怪的年龄上限。

第二行 nn 个用空格分开的数 x1,x2,,xnx_1,x_2,\dots,x_nxix_i 表示第 ii 个地点妖怪的年龄,满足 0xi<A0 \le x_i < A。(年龄是可以为 00 的,例如刚出生的妖怪的年龄为 00

接下来 n1n-1 行,每行三个用空格分开的数 a,b,ca,b,c,表示树上的顶点 aabb 之间有一条权为 cc1c10001 \le c \le 1000)的边,aabb 是顶点编号。

接下来 QQ 行,每行三个用空格分开的数 u,a,bu, a, b。对于这 QQ 行的每一行,用 a,b,Aa, b, A 计算出 LLRR,表示询问“在地方 uu 开店,面向妖怪的年龄区间为 [L,R][L,R] 的方案的方便值是多少”。对于其中第 11 行,LLRR 的计算方法为:L=min(amodA,bmodA)L=\min(a\bmod A,b\bmod A)R=max(amodA,bmodA)R=\max(a\bmod A,b\bmod A)。对于第 22 到第 QQ 行,假设前一行得到的方便值为 ans\mathrm{ans},那么当前行的 LLRR 计算方法为: L=min((a+ans)modA,(b+ans)modA)L=\min((a+\mathrm{ans})\bmod A,(b+\mathrm{ans})\bmod A)
R=max((a+ans)modA,(b+ans)modA)R=\max((a+\mathrm{ans})\bmod A,(b+\mathrm{ans})\bmod A)

Output

对于每个方案,输出一行表示方便值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

1
2
3
4
5
6
7
8
9
10
11

1603
957
7161
9466
3232
5223
1879
1669
1282
0

HINT

对于所有数据,n150000n \le 150000Q200000Q \le 200000A109A \le 10^9

Solution

主席树

xjb维护一波。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

#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;
}