据说还可以动态点分治？
壮哉我大优美树剖！
跟「『2017 山东一轮集训 Day5』距离」一样的 trick。
目的是求路径的交，类似地到根加一然后计算贡献。
此题是对点权在 \([L,R]\) 内的点与某钦定点的距离求和，容易想到转化为前缀和相减的形式，然后对线段树持久化。
并且需要离散化。
（不过直接用 map 好像也是可以的，每次查询的时候 lower/upper_bound 最近的那棵树）
这么神的题居然一遍过了，恨没生在 HNOI2015……
代码： 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
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w ? x = -x : x;
}
const int N = 15e4;
int n,q,lim;
int a[N + 5],ind[N + 5],len;
int to[(N << 1) + 5],val[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
pair<int,int> t[N + 5];
long long lastans;
inline void add(int u,int v,int w)
{
static int tot = 0;
to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],rk[N + 5],w[N + 5];
int cnt[N + 5];
long long dis[N + 5],sum[N + 5];
void dfs1(int p)
{
sz[p] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
dep[to[i]] = dep[p] + 1,dis[to[i]] = dis[p] + val[i],fa[to[i]] = p,w[to[i]] = val[i],dfs1(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[to[i]] > sz[son[p]])
son[p] = to[i];
}
}
void dfs2(int p)
{
static int tot = 0;
rk[id[p] = ++tot] = p;
if(son[p])
top[son[p]] = top[p],dfs2(son[p]);
for(register int i = first[p];i;i = pre[i])
if(!id[to[i]])
top[to[i]] = to[i],dfs2(to[i]);
}
struct node
{
long long sum,val,tag;
int ls,rs;
} seg[(N << 6) + 10];
int rt[N + 5],seg_tot;
void build(int &p,int tl,int tr)
{
p = ++seg_tot;
if(tl == tr)
{
seg[p].val = w[rk[tl]];
return ;
}
int mid = tl + tr >> 1;
build(seg[p].ls,tl,mid),build(seg[p].rs,mid + 1,tr);
seg[p].val = seg[seg[p].ls].val + seg[seg[p].rs].val;
}
void update(int l,int r,int &p,int tl,int tr)
{
seg[++seg_tot] = seg[p],p = seg_tot;
if(l <= tl && tr <= r)
{
seg[p].sum += seg[p].val,++seg[p].tag;
return ;
}
int mid = tl + tr >> 1;
if(l <= mid)
update(l,r,seg[p].ls,tl,mid);
if(r > mid)
update(l,r,seg[p].rs,mid + 1,tr);
seg[p].sum = seg[seg[p].ls].sum + seg[seg[p].rs].sum + seg[p].tag * seg[p].val;
}
inline pair<long long,long long> operator+(const pair<long long,long long> &a,const pair<long long,long long> &b)
{
return make_pair(a.first + b.first,a.second + b.second);
}
pair<long long,long long> query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return make_pair(seg[p].sum,seg[p].val);
int mid = tl + tr >> 1;
pair<long long,long long> ret(0,0);
if(l <= mid)
ret = ret + query(l,r,seg[p].ls,tl,mid);
if(r > mid)
ret = ret + query(l,r,seg[p].rs,mid + 1,tr);
ret.first += ret.second * seg[p].tag;
return ret;
}
long long query(int p,int l,int r)
{
long long ret = sum[r] - sum[l] + dis[p] * (cnt[r] - cnt[l]);
while(p)
ret -= (query(id[top[p]],id[p],rt[r],1,n).first - query(id[top[p]],id[p],rt[l],1,n).first) * 2,p = fa[top[p]];
return ret;
}
int main()
{
read(n),read(q),read(lim);
for(register int i = 1;i <= n;++i)
read(a[i]),ind[i] = a[i];
sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind,t[i] = make_pair(a[i],i);
int u,v,w;
for(register int i = 1;i < n;++i)
read(u),read(v),read(w),add(u,v,w),add(v,u,w);
dep[1] = top[1] = 1,dfs1(1),dfs2(1),build(rt[0],1,n);
sort(t + 1,t + n + 1);
for(register int i = 1,j = 1;rt[i] = rt[i - 1],sum[i] = sum[i - 1],cnt[i] = cnt[i - 1],i <= len;++i)
for(;t[j].first <= i && j <= n;++j)
{
int x = t[j].second;
sum[i] += dis[x],++cnt[i];
while(x)
update(id[top[x]],id[x],rt[i],1,n),x = fa[top[x]];
}
int x,l,r;
while(q--)
{
read(x),read(l),read(r),l = (l + lastans) % lim,r = (r + lastans) % lim;
if(l > r)
swap(l,r);
l = lower_bound(ind + 1,ind + len + 1,l) - ind - 1,r = upper_bound(ind + 1,ind + len + 1,r) - ind - 1;
printf("%lld\n",lastans = query(x,l,r));
}
}