題目描述 Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional roads, such that there is exactly one path between any two p ...
題目描述
Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional roads, such that there is exactly one path between any two pastures. Bessie, a cow who loves her grazing time, often complains about how there is no grass on the roads between pastures. Farmer John loves Bessie very much, and today he is finally going to plant grass on the roads. He will do so using a procedure consisting of M steps (1 <= M <= 100,000).
At each step one of two things will happen:
-
FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or,
- Bessie will ask about how many patches of grass on a particular road, and Farmer John must answer her question.
Farmer John is a very poor counter -- help him answer Bessie's questions!
給出一棵n個節點的樹，有m個操作，操作為將一條路徑上的邊權加一或詢問某條邊的權值。
輸入輸出格式
輸入格式：
-
Line 1: Two space-separated integers N and M
-
Lines 2..N: Two space-separated integers describing the endpoints of a road.
- Lines N+1..N+M: Line i+1 describes step i. The first character of the line is either P or Q, which describes whether or not FJ is planting grass or simply querying. This is followed by two space-separated integers A_i and B_i (1 <= A_i, B_i <= N) which describe FJ's action or query.
輸出格式：
- Lines 1..???: Each line has the answer to a query, appearing in the same order as the queries appear in the input.
輸入輸出樣例
輸入樣例#1： 複製4 6 1 4 2 4 3 4 P 2 3 P 1 3 Q 3 4 P 1 4 Q 2 4 Q 1 4輸出樣例#1： 複製
2 1 2
樹鏈剖分的裸題
但是這個題是在邊上進行操作
我們考慮把邊上的操作轉移到點上
首先想一下最簡單的鏈的情況
對於區間$[l,r]$的操作會影響$r-l+1$個點，但只會影響$r-l$條邊
那麼我們可以把每條邊的邊權都放在與它相連的兩個點中深度較深的點上
所以我們每次修改的時候都對$(l,r]$進行修改
查詢的時候也如此，
具體怎麼實現呢？so easy:joy:
只需要在查詢/修改的時候把左區間+1即可
註意特判一下x==y的情況
#include<iostream> #include<cstdio> #include<cstring> #define ls k<<1 #define rs k<<1|1 #define LL long long int using namespace std; const int MAXN=1e6+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();} return x*f; } int root=1; struct node { int u,v,w,nxt; }edge[MAXN]; int head[MAXN]; int num=1; inline void AddEdge(int x,int y) { edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++; } struct Tree { int l,r,f,w,siz; }T[MAXN]; int a[MAXN],b[MAXN],tot[MAXN],idx[MAXN],deep[MAXN],son[MAXN],top[MAXN],fa[MAXN],cnt=0; void update(int k) { T[k].w=T[ls].w+T[rs].w; } void PushDown(int k) { if(!T[k].f) return ; T[ls].w+=T[k].f*T[ls].siz; T[rs].w+=T[k].f*T[rs].siz; T[ls].f+=T[k].f; T[rs].f+=T[k].f; T[k].f=0; } int dfs1(int now,int f,int dep) { deep[now]=dep; tot[now]=1; fa[now]=f; int maxson=-1; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v==f) continue; tot[now]+=dfs1(edge[i].v,now,dep+1); if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v; } return tot[now]; } void dfs2(int now,int topf) { idx[now]=++cnt; a[cnt]=b[now]; top[now]=topf; if(!son[now]) return ; dfs2(son[now],topf); for(int i=head[now];i!=-1;i=edge[i].nxt) if(!idx[edge[i].v]) dfs2(edge[i].v,edge[i].v); } void Build(int k,int ll,int rr) { T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1; if(ll==rr) { T[k].w=a[ll]; return ; } int mid=(ll+rr)>>1; Build(ls,ll,mid); Build(rs,mid+1,rr); update(k); } void IntervalAdd(int k,int ll,int rr,int val) { if(ll<=T[k].l&&T[k].r<=rr) { T[k].w+=T[k].siz*val; T[k].f+=val; return ; } PushDown(k); int mid=(T[k].l+T[k].r)>>1; if(ll<=mid) IntervalAdd(ls,ll,rr,val); if(rr>mid) IntervalAdd(rs,ll,rr,val); update(k); } int IntervalAsk(int k,int ll,int rr) { int ans=0; if(ll<=T[k].l&&T[k].r<=rr) { ans+=T[k].w; return ans; } PushDown(k); int mid=(T[k].l+T[k].r)>>1; if(ll<=mid) ans+=IntervalAsk(ls,ll,rr); if(rr>mid) ans+=IntervalAsk(rs,ll,rr); return ans; } int TreeSum(int x,int y) { int ans=0; while(top[x]!=top[y])//不在同一條鏈內 { if(deep[top[x]]<deep[top[y]]) swap(x,y); ans+=IntervalAsk(1,idx[top[x]],idx[x]); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); if(x==y) return ans; ans+=IntervalAsk(1,idx[x]+1,idx[y]);//需要修改的地方 return ans; } void TreeAdd(int x,int y) { while(top[x]!=top[y])//不在同一條鏈內 { if(deep[top[x]]<deep[top[y]]) swap(x,y); IntervalAdd(1,idx[top[x]],idx[x],1); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); if(x==y) return ; IntervalAdd(1,idx[x]+1,idx[y],1);//需要修改的地方 } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); int N=read(),M=read(); for(int i=1;i<=N-1;i++) { int x=read(),y=read(); AddEdge(x,y);AddEdge(y,x); } dfs1(root,0,1); dfs2(root,root); Build(1,1,N); while(M--) { char opt[3];int x,y; scanf("%s",opt);x=read();y=read(); if(opt[0]=='P') TreeAdd(x,y); else printf("%d\n",TreeSum(x,y)); } return 0; }
