Description
风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。
很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 n 个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，其中第 i 个地方的妖怪年龄是 $x_i$。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 u（u 为编号），然后在 u 开一家面向年龄在 L 到 R 之间（即年龄大于等于 L、小于等于 R）的妖怪的店。也有可能 u 这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪，到点 u 的距离的和是多少（妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和） ，幽香把这个称为这个开店方案的方便值。
幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。
Simplified Description
给你一棵 $n$ 个点树，每个点都有一个权值。 有 $m$ 次询问，每次询问给你一个点，问这个点到所有权值在 $L$ 到 $R$ 之间 的点的距离和为多少。强制在线。
Idea
先将答案差分，考虑权值在 $[1,r]$ 内点到给定点的距离之和，可以用如下式子表示
$$\sum_{i=1}^r (dep_u+dep_i-2\times dep_{lca})=\sum_{i=1}^r dep_i+dep_u\times r+\sum dep_{lca}$$
发现除了 $\sum dep_{lca}$ 都挺好求的。
这时我们可以将点按照权值排序，然后依次插入。插入后它会给每个节点造成它自己深度的贡献，用树链剖分套线段树的区间操作即可。
因为我们需要询问在一段区间内的答案，因此需要将线段树可持久化。此时我们换用带修主席树维护。
时间复杂度 $\Theta(n\log^2n)$。
Code
#include <bits/stdc++.h>
#define N 200010
#define inf INT_MAX
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
int son[N],fa[N],siz[N],top[N],fv[N],num[N];
int cnt,head[N],id[N],rt[N],n,q,A;
ll sdep[N],dep[N],lastans;
ll read(){
ll x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
struct Mon{
int age,id;
Mon(int a=0,int b=0){
age=a,id=b;
}
bool operator < (const Mon &x) const{
return age<x.age;
}
}mon[N];
struct Node{
int ls,rs,lazy;
ll sum,esum;
}t[N<<7];
struct Edge{
int to,next,val;
Edge(int a=0,int b=0,int c=0){
to=a,next=b,val=c;
}
}l[N<<1];
void Add(int a,int b,int c){
l[++cnt]=Edge(b,head[a],c);head[a]=cnt;
l[++cnt]=Edge(a,head[b],c);head[b]=cnt;
}
void Pre_Work(int u,int f){
fa[u]=f,siz[u]=1;
int mx=-1;
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;if (v==f) continue;
dep[v]=dep[u]+l[i].val;fv[v]=l[i].val;
Pre_Work(v,u);siz[u]+=siz[v];
if (siz[v]>mx) mx=siz[v],son[u]=v;
}
}
void Re_Build(int u,int topf){
top[u]=topf,id[u]=++cnt;num[cnt]=fv[u];
if (son[u]) Re_Build(son[u],topf);
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v!=son[u]&&v!=fa[u])
Re_Build(v,v);
}
}
void Build(int &p,int l,int r){
int pre=p;p=++cnt;t[p]=t[pre];
if (l==r) {t[p].esum=num[l];return;}
Build(t[p].ls,l,mid);
Build(t[p].rs,mid+1,r);
t[p].esum=t[t[p].ls].esum+t[t[p].rs].esum;
}
void Update(int &p,int l,int r,int L,int R){
int pre=p;p=++cnt;t[p]=t[pre];
if (L<=l&&r<=R){
++t[p].lazy;
t[p].sum+=t[p].esum;
return;
}
if (mid>=L) Update(t[p].ls,l,mid,L,R);
if (mid<R) Update(t[p].rs,mid+1,r,L,R);
t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum+t[p].esum*t[p].lazy;
}
ll Query(int p,int l,int r,int L,int R,int add){
if (L<=l&&r<=R) return t[p].sum+t[p].esum*add;
add+=t[p].lazy;
if (mid>=R) return Query(t[p].ls,l,mid,L,R,add);
if (mid<L) return Query(t[p].rs,mid+1,r,L,R,add);
return Query(t[p].ls,l,mid,L,R,add)+Query(t[p].rs,mid+1,r,L,R,add);
}
ll Path_Query(int u,int ver){
ll res=0;
while(top[u]!=1){
res+=Query(rt[ver],1,n,id[top[u]],id[u],0);
u=fa[top[u]];
}
res+=Query(rt[ver],1,n,1,id[u],0);
return res;
}
void Path_Update(int u,int ver){
while(top[u]!=1){
Update(rt[ver],1,n,id[top[u]],id[u]);
u=fa[top[u]];
}
Update(rt[ver],1,n,1,id[u]);
}
ll Solve(int u,int ver){
return sdep[ver]+dep[u]*ver-2*Path_Query(u,ver);
}
int main(){
n=read(),q=read(),A=read();
for (int i=1;i<=n;++i)
mon[i].age=read(),mon[i].id=i;
for (int i=2,a,b,c;i<=n;++i)
a=read(),b=read(),c=read(),
Add(a,b,c);cnt=0;
Pre_Work(1,0);Re_Build(1,1);cnt=0;
sort(mon+1,mon+1+n);
Build(rt[0],1,n);
for (int i=1;i<=n;++i)
sdep[i]=sdep[i-1]+dep[mon[i].id],
rt[i]=rt[i-1],Path_Update(mon[i].id,i);
for (int i=1;i<=q;++i){
int u;
ll l,r;
u=read(),l=read(),r=read();
(l+=lastans)%=A,(r+=lastans)%=A;
int L=min(l,r),R=max(l,r);
l=lower_bound(mon+1,mon+1+n,Mon(L,0))-mon,
r=upper_bound(mon+1,mon+1+n,Mon(R,inf))-mon-1;
printf("%lld\n",lastans=Solve(u,r)-Solve(u,l-1));
}
}