题解 P3459 【[POI2007]MEG-Megalopolis】

【POI补全计划#43 POI2007 MEG】 我们来尝试暴力一点的做法：树剖 基本上就是无脑搞，将问题转换为： 维护树上两个操作 1.树上单条边权-1 2.查询树上点到根路径上权值和 就当是用作树链剖分模板题了 P.S.单点修改链上查询一般可以转化为dfs序，而且dfs序常数一般比树链剖分小（楼下的解法） 贴代码 ```cpp #include<iostream> #include<cstdio> #include<map> using namespace std; const int MAXN=250010; struct node { int l,r,sum; node *lson,*rson; }*root,pool[MAXN*4]; int top; node* build(int l,int r) { node *tmp=&pool[++top]; tmp->l=l;tmp->r=r; tmp->sum=r-l+1; if(l!=r) { int mid=(l+r)/2; tmp->lson=build(l,mid); tmp->rson=build(mid+1,r); } return tmp; } void change(node *cur,int pos)//minus 1 { cur->sum--; if(cur->l==cur->r)return; if(cur->lson->r>=pos)change(cur->lson,pos); else change(cur->rson,pos); } int query(node *cur,int l,int r) { if(cur->l==l&&cur->r==r) return cur->sum; if(cur->lson->r>=r)return query(cur->lson,l,r); else if(cur->rson->l<=l)return query(cur->rson,l,r); else return query(cur->lson,l,cur->lson->r)+query(cur->rson,cur->rson->l,r); } struct edge { int v,id; edge *next; }*h[MAXN],epool[MAXN*2]; int etop; inline void addedge(int u,int v) { edge *tmp=&epool[++etop];tmp->v=v;tmp->next=h[u];h[u]=tmp; edge *pmt=&epool[++etop];pmt->v=u;pmt->next=h[v];h[v]=pmt; } int dep[MAXN],siz[MAXN],pa[MAXN],maxson[MAXN],paedge[MAXN],pathroot[MAXN]; void dfs1(int u) { siz[u]=1; for(edge *tmp=h[u];tmp;tmp=tmp->next) { if(!dep[tmp->v]) { dep[tmp->v]=dep[u]+1; pa[tmp->v]=u; dfs1(tmp->v); siz[u]+=siz[tmp->v]; if(siz[tmp->v]>siz[maxson[u]])maxson[u]=tmp->v; } } } int cur; void dfs2(int u) { if(maxson[u]) { paedge[maxson[u]]=++cur; pathroot[maxson[u]]=pathroot[u]; dfs2(maxson[u]); } for(edge *tmp=h[u];tmp;tmp=tmp->next) { if(tmp->v!=maxson[u]&&dep[tmp->v]==dep[u]+1) { paedge[tmp->v]=++cur; pathroot[tmp->v]=tmp->v; dfs2(tmp->v); } } } inline int qtree(int x) { int ans=0; while(x) { ans+=query(root,paedge[pathroot[x]],paedge[x]); x=pa[pathroot[x]]; } return ans; } int main() { int n,q,a,b; char ch; scanf("%d",&n); for(int i=1;i<=n-1;i++) { scanf("%d%d",&a,&b); addedge(a,b); } dep[1]=1; dfs1(1); pathroot[1]=1; dfs2(1); root=build(0,n-1); scanf("%d",&q); for(int i=1;i<=n+q-1;i++) { scanf(" %c",&ch); if(ch=='W') { scanf("%d",&a); printf("%d\n",qtree(a)-1); } else { scanf("%d%d",&a,&b); change(root,paedge[b]); } } return 0; } ```