表示看不太清.

概括题意

树上维护区间修改与区间和查询.

很明显树剖裸题,切掉,细节处错误T了好久 TAT

代码

#include
    
     #include
     
      #include
      
       #include
       
        #define int long long#define R register#define ls o<<1#define rs o<<1|1#define N 500008using namespace std;inline void in(int &x){    int f=1;x=0;char s=getchar();    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}    while(isdigit(s)){x=x*10+s-'0';s=getchar();}    x*=f;}int n,m,head[N],tot,f[N],son[N],size[N],depth[N];struct cod{int u,v;}edge[N<<2];inline void add(int x,int y){    edge[++tot].u=head[x];    edge[tot].v=y;    head[x]=tot;}void dfs1(int u,int fa){    f[u]=fa;depth[u]=depth[fa]+1;size[u]=1;    for(R int i=head[u];i;i=edge[i].u)    {        if(edge[i].v==fa)continue;        dfs1(edge[i].v,u);        size[u]+=size[edge[i].v];        if(son[u]==-1 or size[son[u]]
        
         >1;        tg[ls]+=tg[o];tg[rs]+=tg[o];        tr[ls]+=(mid-l+1)*tg[o];        tr[rs]+=(r-mid)*tg[o];        tg[o]=0;    }}void change(int o,int l,int r,int x,int y,int z){    if(x<=l and y>=r)    {        tr[o]+=(r-l+1)*z;        tg[o]+=z;        return;    }    down(o,l,r);    int mid=(l+r)>>1;    if(x<=mid)change(ls,l,mid,x,y,z);    if(y>mid)change(rs,mid+1,r,x,y,z);    up(o);}int query(int o,int l,int r,int x,int y){    if(x<=l and y>=r)return tr[o];    down(o,l,r);    int mid=(l+r)>>1,res=0;    if(x<=mid)res+=query(ls,l,mid,x,y);    if(y>mid)res+=query(rs,mid+1,r,x,y);    return res;}inline void tchange(int x,int y,int z){    int fx=top[x],fy=top[y];    while(fx!=fy)    {        if(depth[fx]>depth[fy])        {            change(1,1,idx,dfn[fx],dfn[x],z);            x=f[fx];        }        else        {            change(1,1,idx,dfn[fy],dfn[y],z);            y=f[fy];        }        fx=top[x],fy=top[y];    }    if(x==y)return;    if(dfn[x]>dfn[y])swap(x,y);    change(1,1,idx,dfn[x]+1,dfn[y],z);}inline int tquery(int x,int y){    int fx=top[x],fy=top[y],res=0;    while(fx!=fy)    {        if(depth[fx]>depth[fy])        {            res+=query(1,1,idx,dfn[fx],dfn[x]);            x=f[fx];        }        else        {            res+=query(1,1,idx,dfn[fy],dfn[y]);            y=f[fy];        }        fx=top[x],fy=top[y];    }    if(x==y)return res;    if(dfn[x]>dfn[y])swap(x,y);    res+=query(1,1,idx,dfn[x]+1,dfn[y]);    return res;}char s[10];signed main(){    in(n),in(m);memset(son,-1,sizeof son);    for(R int i=1,x,y;i