一开始想着二维线段树+二次换根来着，然而空间不够并且强制在线

然后就想到了一个比较好的计算方式，详见

就是类似这个统计距离和的方法，不过这次是有边权的，区间修改的话，预处理路径的长度就好了

然后发现还是不好做，看题解去

然后看到了动态点分治（本人过弱，听懂了就是不会写代码，就一直搁着）

还好有拿那个思路写的，先树链剖分用颗主席树维护就好了，才发现可以将年龄那一维用主席树前缀和处理掉

但是空间依然很紧，用一下标记永久化（太久没写标记永久化了，写了好久才写对）

代码：

#include
    
     #include
     
      #include
      
       using namespace std;void read(int &x) {    char ch; bool ok;    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}#define rg registerconst int maxn=2e5+10;long long ss[maxn],dis[maxn],sum[maxn*30],lastans,s[maxn];int pre[maxn*2],nxt[maxn*2],h[maxn],v[maxn*2],cnt,tot,f[maxn],ans;int n,m,A,dep[maxn],size[maxn],w[maxn],top[maxn],id[maxn],tmp;int rt[maxn],ls[maxn*30],rs[maxn*30],tag[maxn*30];struct oo{int x,id;}a[maxn];bool cmp(oo a,oo b){return a.x
       
        dep[x]&&size[pre[i]]>size[k])k=pre[i];    if(!k)return ;dfs1(k,ff);    for(rg int i=h[x];i;i=nxt[i])        if(dep[pre[i]]>dep[x]&&pre[i]!=k)dfs1(pre[i],pre[i]);}void change(int x,int &k,int l,int r,int a,int b,int id){    k=++tot,ls[k]=ls[x],rs[k]=rs[x],tag[k]=tag[x],sum[k]=sum[x];    if(a<=l&&b>=r){tag[k]++;return ;}    int mid=(l+r)>>1;sum[k]+=ss[min(r,b)]-ss[max(l,a)-1];    if(a<=mid)change(ls[x],ls[k],l,mid,a,b,id);    if(b>mid)change(rs[x],rs[k],mid+1,r,a,b,id);}void modify(int k,int x,int y){    while(top[x]!=top[y])    {        if(dep[top[x]]
        
         id[y])swap(x,y);    change(rt[k],rt[k],1,n,id[x],id[y],k);}long long get(int x,int &k,int l,int r,int a,int b,int now){    long long ans=0,mid=(l+r)>>1;    if(a<=l&&b>=r)return (now+tag[k]-tag[x])*(ss[r]-ss[l-1])+sum[k]-sum[x];    if(a<=mid)ans+=get(ls[x],ls[k],l,mid,a,b,now+tag[k]-tag[x]);    if(b>mid)ans+=get(rs[x],rs[k],mid+1,r,a,b,now+tag[k]-tag[x]);    return ans;}long long qsum(int a,int b,int x,int y){    long long ans=0;    while(top[x]!=top[y])    {        if(dep[top[x]]
         
          id[y])swap(x,y); ans+=get(rt[a],rt[b],1,n,id[x],id[y],0); return ans;}signed main(){ read(n),read(m),read(A); for(rg int i=1;i<=n;i++)read(a[i].x),a[i].id=i,w[i]=a[i].x; for(rg int i=1,x,y,z;i