[文章目录]
Description
幻想乡的地图是一个树形结构，幻想乡一共有 n个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 u（u为编号），然后在 u开一家面向年龄在 L到R 之间（即年龄大于等于 L、小于等于 R）的妖怪的店。也有可能 u这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪，到点 u 的距离的和是多少（妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和） ，幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。n<=150000，Q<=200000，强制在线
动态点分治
对于每个点维护关于年龄的到根节点的深度和以及点的个数，同时维护到其分治的父亲节点关于不同年龄的深度和以及个数，可以用链表按照从小到大维护块中节点的年龄以及对应深度的前缀和，每次将区间差分后二分找位置即可。
查询时容斥即可。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pb push_back
#define N 151000
int n,m,mod,tot,cl[N];
int head[N],to[N<<1],nxt[N<<1],data[N<<1],cnt;
inline void add(int x,int y,int z) {to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; data[cnt]=z;}
int pos[N],dep[N],lca[N<<1][20],Log[N<<1],bin[20];
void dfs(int x,int pre)
{
lca[++tot][0]=dep[x]; pos[x]=tot;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dep[to[i]]=dep[x]+data[i],dfs(to[i],x),lca[++tot][0]=dep[x];
}
int dis(int x,int y)
{
if(pos[x]>pos[y]) swap(x,y);
int lo=Log[pos[y]-pos[x]+1];
return dep[x]+dep[y]-(min(lca[pos[x]][lo],lca[pos[y]-bin[lo]+1][lo])<<1);
}
bool cmp(int x,int y){return cl[x]<cl[y];}
vector<int>r1[N],r2[N];
vector<ll>s1[N],s2[N];
ll S;
int root,nn,ran[N],siz[N],msi[N],fa[N];
bool vis[N];
void getroot(int x,int pre)
{
siz[x]=1,msi[x]=0;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
getroot(to[i],x),siz[x]+=siz[to[i]],msi[x]=max(msi[x],siz[to[i]]);
msi[x]=max(msi[x],nn-siz[x]);
if(msi[x]<msi[root]) root=x;
}
void Dfs(int x,int pre)
{
ran[++tot]=x,siz[x]=1;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
Dfs(to[i],x),siz[x]+=siz[to[i]];
}
ll query(vector<int> &v,int x)
{
int l=0,r=v.size(),mid;
while(l<r)
{
mid=(l+r)>>1;
if(v[mid]<=x) l=mid+1;
else r=mid;
}
return l-1;
}
void build(int x,int pre)
{
fa[x]=pre,tot=0; Dfs(x,pre); vis[x]=1; sort(ran+1,ran+tot+1,cmp);
if(pre) for(int i=1;i<=tot;++i) r2[x].pb(cl[ran[i]]),
s2[x].pb(s2[x][s2[x].size()-1]+dis(pre,ran[i]));
for(int i=1;i<=tot;++i) r1[x].pb(cl[ran[i]]),
s1[x].pb(s1[x][s1[x].size()-1]+dis(x,ran[i]));
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]])
nn=siz[to[i]],root=0,getroot(to[i],x),build(root,x);
}
int main()
{
scanf("%d%d%d",&n,&m,&mod);
int i,j;
for(i=1;i<=n;++i) scanf("%d",cl+i);
int x,y,z;
for(i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dfs(1,0);
for(i=2;i<=tot;++i) Log[i]=Log[i>>1]+1;
for(i=0;i<=Log[tot];++i) bin[i]=1<<i;
for(i=1;i<=Log[tot];++i)
for(j=1;j+bin[i]-1<=tot;++j)
lca[j][i]=min(lca[j][i-1],lca[j+bin[i-1]][i-1]);
for(i=1;i<=n;++i) s1[i].pb(0),s2[i].pb(0),r1[i].pb(-1),r2[i].pb(-1);
msi[0]=0x3f3f3f3f,nn=n; getroot(1,0); build(root,0);
ll l,r,ans=0; int R,L;
while(m--)
{
scanf("%d%lld%lld",&x,&l,&r);
l=(l+ans)%mod; r=(r+ans)%mod;
if(l>r) swap(l,r);
for(ans=0,i=x;i;i=fa[i])
{
R=query(r1[i],r); L=query(r1[i],l-1); S=R-L;
ans+=s1[i][R]-s1[i][L]+S*dis(i,x);
if(fa[i])
{
R=query(r2[i],r); L=query(r2[i],l-1); S=R-L;
ans-=s2[i][R]-s2[i][L]+S*dis(fa[i],x);
}
}
printf("%lld\n",ans);
}
return 0;
}