求出DFS序
修路相當于區間減，點詢
樹狀數組維護之

操作數要加(N-1)

#include <cstdio> #include <cassert> #include <string>using namespace std;int read(){int x=0, f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=-f;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*f; }const int MAXN=250111; const int MAXM=250111;int N, M;struct Vert{int FE;int Dps, Dpr;int Dep; } V[MAXN];struct Edge{int x, y, next; } E[MAXN<<1];int Ecnt=0;void addE(int a, int b){++Ecnt;E[Ecnt].x=a;E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt; }int Dfn[MAXN], DFN=0;void DFS(int at, int f=0){++DFN;Dfn[DFN]=at;V[at].Dps=DFN;for(int k=V[at].FE, to;k>0;k=E[k].next){to=E[k].y;if(to==f) continue;V[to].Dep=V[at].Dep+1;DFS(to, at);}V[at].Dpr=DFN; }int C[MAXN];int lowbit(int a){return a&(-a); }void Add(int at, int v){//cout << "Add " << at << " " << v << endl;for(int i=at;i<=N;i+=lowbit(i))C[i]+=v; }int Ask(int at){//cout << "Ask " << at << endl;int ret=0;for(int i=at;i>0;i-=lowbit(i))ret+=C[i];return ret; }char com[10]; int p, q;int main(){N=read();for(int i=1, a, b;i<N;++i){a=read();b=read();addE(a, b);addE(b, a);}V[1].Dep=1;DFS(1);assert(DFN==N);for(int i=1, j;i<=N;++i){j=Dfn[i];Add(i, V[j].Dep);Add(i+1, -V[j].Dep);}M=read();M+=(N-1);/**/while(M--){scanf("%s", com);if(com[0]=='A'){p=read();q=read();if(V[p].Dep<V[q].Dep) swap(p, q);Add(V[p].Dps, -1);Add(V[p].Dpr+1, 1);}else{p=read();/*p=Dfn[p];*/p=V[p].Dps;printf("%d\n", Ask(p)-1/**/);}}return 0; }

轉載于:https://www.cnblogs.com/Pickupwin/p/9095640.html

總結

以上是生活随笔為你收集整理的BZOJ 1103 大都市MEG的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。