树链剖分好题。

对于每个点维护一个值vivi，当考虑点i时我们将它到根的路径上的所有数的v值+1。

这样维护下来v和dep的值是相等的。

当这个更新到达点i时，从1到z这条路径的v值之和就是∑ij=1dep[lca(j,z)]∑j=1idep[lca(j,z)]

这样的话一个询问(l,r,z)可以转化成calc(1,r,z)-calc(1.l-1,z)。

这样就可以离线用树剖维护了。

代码：

#include
    
     #define lc (p<<1)#define rc (p<<1|1)#define mid (T[p].l+T[p].r>>1)#define N 50005#define mod 201314using namespace std;int n,m,first[N],dep[N],top[N],hson[N],fa[N],siz[N],num[N],cnt=0,tot=0,sig=0,ans[N];struct edge{
   int v,next;}e[N<<1];struct Q{
   int id,pos,tmp,z;}q[N<<1];struct Node{
   int l,r,sum,lz;}T[N<<2];inline int read(){    int ans=0;    char ch=getchar();    while(!isdigit(ch))ch=getchar();    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return ans;}inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}inline void dfs1(int p){    siz[p]=1;    for(int i=first[p];i;i=e[i].next){        int v=e[i].v;        dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];        if(siz[v]>siz[hson[p]])hson[p]=v;    }}inline void dfs2(int p,int tp){    top[p]=tp,num[p]=++sig;    if(!hson[p])return;    dfs2(hson[p],tp);    for(int i=first[p];i;i=e[i].next){        int v=e[i].v;        if(v!=hson[p])dfs2(v,v);    }}inline void pushup(int p){T[p].sum=(T[lc].sum+T[rc].sum)%mod;}inline void pushnow(int p,int v){(T[p].sum+=v*(T[p].r-T[p].l+1))%=mod,(T[p].lz+=v)%=mod;}inline void pushdown(int p){
   if(T[p].lz)pushnow(lc,T[p].lz),pushnow(rc,T[p].lz),T[p].lz=0;}inline void build(int p,int l,int r){    T[p].l=l,T[p].r=r;    if(l==r)return;    build(lc,l,mid),build(rc,mid+1,r);}inline void update(int p,int ql,int qr,int v){    if(ql>T[p].r||qr
     
      mid)update(rc,ql,qr,v);    else update(lc,ql,mid,v),update(rc,mid+1,qr,v);    pushup(p);}inline int query(int p,int ql,int qr){    if(ql>T[p].r||qr
      
       mid)return query(rc,ql,qr);    return (query(lc,ql,mid)+query(rc,mid+1,qr))%mod;}inline void change(int x,int y,int v){    while(top[x]!=top[y]){        if(dep[top[x]]