给出一棵 \(N\) 个节点的树,有 \(M\) 个操作,操作为将一条路径上的边权加一或询问某条边的权值。
点差分与边差分的区别是:点差分计入 \(lca\) ,边差分不计 \(lca\)。
模板树链剖分是对点统计,类似点差分。
本题是对边统计,只需要去掉 \(lca\) 的计算即可。
如觉怪异,请见谅。
#include<cstdio> #include<iostream> using namespace std; int read(){ int x=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x; } const int Maxn=1e5+5; const int Inf=0x3f3f3f3f; namespace A{ struct Adjacency_List{ int nxt,t; }tr[Maxn<<1]; int h[Maxn]; int tot; void Add(int x,int y){ tr[++tot].nxt=h[x]; tr[tot].t=y; h[x]=tot; } } namespace B{ struct Segment_Tree{ int l,r; int val; int lazy; }tr[Maxn<<2]; inline int ls(int k){return k<<1;} inline int rs(int k){return k<<1|1;} inline int len(int k){return tr[k].r-tr[k].l+1;} inline void push_up(int k){ tr[k].val=tr[ls(k)].val+tr[rs(k)].val; } inline void push_down(int k){ if(!tr[k].lazy)return ; tr[ls(k)].val+=len(ls(k))*tr[k].lazy; tr[ls(k)].lazy+=tr[k].lazy; tr[rs(k)].val+=len(rs(k))*tr[k].lazy; tr[rs(k)].lazy+=tr[k].lazy; tr[k].lazy=0; } void build(int k,int l,int r){ tr[k].l=l,tr[k].r=r; if(l==r)return; int mid=(l+r)>>1; build(ls(k),l,mid); build(rs(k),mid+1,r); } int query(int k,int ql,int qr){ // printf("(%d) [%d, %d] = %d\n",k,tr[k].l,tr[k].r,tr[k].val); if(ql<=tr[k].l&&tr[k].r<=qr) return tr[k].val; push_down(k); int mid=(tr[k].l+tr[k].r)>>1; int ret=0; if(ql<=mid)ret+=query(ls(k),ql,qr); if(qr>mid)ret+=query(rs(k),ql,qr); return ret; } void modifit(int k,int ql,int qr,int d){ if(ql<=tr[k].l&&tr[k].r<=qr){ tr[k].val+=len(k)*d; tr[k].lazy+=d; // printf("(%d) [%d, %d] = %d\n",k,tr[k].l,tr[k].r,tr[k].val); return ; } push_down(k); int mid=(tr[k].l+tr[k].r)>>1; if(ql<=mid)modifit(ls(k),ql,qr,d); if(qr>mid)modifit(rs(k),ql,qr,d); push_up(k); // printf("(%d) [%d, %d] = %d\n",k,tr[k].l,tr[k].r,tr[k].val); } } struct node{ int id; int fa,son; int dep,top; int sz; }p[Maxn]; int tot; void dfs1(int x,int fa){ p[x].fa=fa; p[x].dep=p[fa].dep+1; p[x].sz=1; int k=-Inf; for(int i=A::h[x];i;i=A::tr[i].nxt){ int y=A::tr[i].t; if(y==fa)continue; dfs1(y,x); p[x].sz+=p[y].sz; if(p[y].sz>k){ k=p[y].sz; p[x].son=y; } } } void dfs2(int x,int fa){ p[x].id=++tot; if(p[x].son){ int y=p[x].son; p[y].top=p[x].top; dfs2(y,x); } for(int i=A::h[x];i;i=A::tr[i].nxt){ int y=A::tr[i].t; if(y==fa)continue; if(y==p[x].son)continue; p[y].top=y; dfs2(y,x); } } void P(int x,int y){ while(p[x].top!=p[y].top){ if(p[p[x].top].dep<p[p[y].top].dep)swap(x,y); // printf("In P : %d %d -> %d %d\n",p[x].top,x,p[p[x].top].id,p[x].id); // printf("In P : x = %d, y = %d\n",x,y); B::modifit(1,p[p[x].top].id,p[x].id,1); x=p[p[x].top].fa; } if(p[x].dep>p[y].dep)swap(x,y); // printf("In P : %d %d -> %d (%d) %d\n",x,y,p[x].id+1,p[x].id,p[y].id); B::modifit(1,p[x].id+1,p[y].id,1); } int Q(int x,int y){ int ret=0; while(p[x].top!=p[y].top){ if(p[p[x].top].dep<p[p[y].top].dep)swap(x,y); // printf("In Q : %d %d -> %d %d\n",p[x].top,x,p[p[x].top].id,p[x].id); ret+=B::query(1,p[p[x].top].id,p[x].id); x=p[p[x].top].fa; } if(p[x].dep>p[y].dep)swap(x,y); // printf("In Q : %d %d -> %d (%d) %d\n",x,y,p[x].id+1,p[x].id,p[y].id); ret+=B::query(1,p[x].id+1,p[y].id); return ret; } int main(){ int n=read(); int m=read(); for(int i=1;i<n;i++){ int x=read(); int y=read(); A::Add(x,y); A::Add(y,x); } p[1].top=1; dfs1(1,0); dfs2(1,0); B::build(1,1,n); while(m--){ char str[2]; scanf("%s",str); int x=read(),y=read(); if(str[0]=='P')P(x,y); else printf("%d\n",Q(x,y)); } return 0; }