题目描述：
风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到
人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的
想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面
向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 n
个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，
其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙，所以它们并
不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一
样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就
比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以
幽香打算选择一个地方 u（u为编号），然后在 u开一家面向年龄在 L到R 之间（即
年龄大于等于 L、小于等于 R）的妖怪的店。也有可能 u这个地方离这些妖怪比较
远，于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪，到点 u 的距离的和是多
少（妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和） ，幽香把这个
称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里，八云紫倒是准
备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。
算法标签：树剖，主席树
思路：
考虑如果没有年龄限制，答案为总点数*d[u]+∑d[i]-∑d[lca(u,i)]。
加上年龄限制，前两个值比较好维护，对于第三个我们考虑用主席树，对于每一个lca，相当于我们把i到根的路径覆盖，取u到根的路径上被覆盖的权值和，即为答案，用主席树统计。
第一次写树剖套主席树呢
以下代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=150005;LL ans,s[N],sd[N]; struct node{int age,id;}b[N];struct data{int l,r,num;LL sum;}t[N*100]; int sz[N],fa[N],son[N],top[N],dfn[N],num[N],cnt,tag[N],c[N],A; int n,q,head[N],ne[N<<1],to[N<<1],w[N<<1],val[N],tot,nt,dist[N],rt[N]; il int read(){int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;} bool cmp(node t1,node t2){return t1.age<t2.age||(t1.age==t2.age&&t1.id<t2.id);} il void insert(int x,int y,int z){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;} il void dfs1(int x){ sz[x]=1;int maxn=-1; for(int i=head[x];i;i=ne[i]){ if(fa[x]==to[i])continue; fa[to[i]]=x;dist[to[i]]=dist[x]+w[i]; dfs1(to[i]);sz[x]+=sz[to[i]];val[to[i]]=w[i]; if(maxn<sz[to[i]])son[x]=to[i],maxn=sz[to[i]]; } } il void dfs2(int x,int root){ dfn[x]=++tot;num[tot]=x;top[x]=root; if(!son[x])return;dfs2(son[x],root); for(int i=head[x];i;i=ne[i]){ if(dfn[to[i]])continue; dfs2(to[i],to[i]); } } il void Ia(int &x,int y,int l,int r,int ql,int qr){ t[x=++nt]=t[y]; if(ql==l&&r==qr){t[x].num++;return;} int mid=(l+r)>>1;t[x].sum+=s[qr]-s[ql-1]; if(qr<=mid)Ia(t[x].l,t[y].l,l,mid,ql,qr); else if(mid<ql)Ia(t[x].r,t[y].r,mid+1,r,ql,qr); else Ia(t[x].l,t[y].l,l,mid,ql,mid),Ia(t[x].r,t[y].r,mid+1,r,mid+1,qr); } il void Ta(int u,int x){ rt[u]=rt[u-1]; while(x>1){ Ia(rt[u],rt[u],1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } } il LL Iq(int x,int y,int l,int r,int ql,int qr){ LL res=1ll*(t[y].num-t[x].num)*(s[qr]-s[ql-1]); if(ql==l&&r==qr)return res+t[y].sum-t[x].sum; if(!x&&!y)return 0;int mid=(l+r)>>1; if(qr<=mid)return res+Iq(t[x].l,t[y].l,l,mid,ql,qr); if(mid<ql)return res+Iq(t[x].r,t[y].r,mid+1,r,ql,qr); return res+Iq(t[x].l,t[y].l,l,mid,ql,mid)+Iq(t[x].r,t[y].r,mid+1,r,mid+1,qr); } il LL Tq(int x,int y,int u){ LL res=0; while(u>1){ res+=Iq(x,y,1,n,dfn[top[u]],dfn[u]); u=fa[top[u]]; } return res; } int main() { n=read();q=read();A=read(); for(int i=1;i<=n;i++)b[i].age=read(),b[i].id=i; sort(b+1,b+1+n,cmp); for(int i=1;i<n;i++){ int x=read(),y=read(),z=read(); insert(x,y,z);insert(y,x,z); } dfs1(1);dfs2(1,1); for(int i=1;i<=n;i++)s[i]=s[i-1]+val[num[i]],sd[i]=sd[i-1]+dist[b[i].id]; for(int i=1;i<=n;i++)Ta(i,b[i].id),c[i]=b[i].age; while(q--){ int u=read(),l=read(),r=read(); l=(1ll*l+ans)%A;r=(1ll*r+ans)%A; if(l>r)swap(l,r); l=lower_bound(c+1,c+1+n,l)-c; r=upper_bound(c+1,c+1+n,r)-c-1; ans=sd[r]-sd[l-1]+1ll*(r-l+1)*dist[u]-2*Tq(rt[l-1],rt[r],u); printf("%lld ",ans); } return 0; }