BZOJ4196 NOI2015 软件包管理器 树链剖分

题意：给定一颗树，维护：1、给定一个节点，求该节点到根的路径上总点数-点权和，并将路径上的所有点的权值赋为1 2、给定一个节点，求该节点子树的点权和，并将子树中所有点的权值赋为0

题解：链剖裸题

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;const int MAXN=100000+2;
struct HASH{int u;HASH *next;HASH(){}HASH(int _u,HASH *_next):u(_u),next(_next){}
}mem[MAXN*2];
struct NODE{int f,b,c,s,m,l,r;HASH *child;
}node[MAXN];
typedef struct TREE{int l,r,s,a;TREE *lchild,*rchild;TREE(){}TREE(int _l,int _r):l(_l),r(_r),s(0),a(-1),lchild(0),rchild(0){}
} *ROOT;
ROOT root;
int N,Q,cnt;
char S[20+2];void Insert(int u,int v){ node[u].child=&(mem[cnt++]=HASH(v,node[u].child));}void DFS1(int f,int x){node[x].c=1,node[x].s=-1;for(HASH *p=node[x].child;p;p=p->next)if(p->u!=f){DFS1(x,p->u);node[x].c+=node[p->u].c;if(node[x].s==-1 || node[p->u].c>node[node[x].s].c) node[x].s=p->u;}
}void DFS2(int f,int x,int b){node[x].f=f,node[x].b=b,node[x].m=node[x].l=node[x].r=++cnt;if(node[x].s!=-1) DFS2(x,node[x].s,b);for(HASH *p=node[x].child;p;p=p->next){if(p->u!=f && p->u!=node[x].s) DFS2(x,p->u,p->u);node[x].r=max(node[x].r,node[p->u].r);}
}void Build(ROOT &x,int l,int r){x=new TREE(l,r);if(l==r) return;int m=(l+r)>>1;Build(x->lchild,l,m),Build(x->rchild,m+1,r);
}void Pushup(ROOT &x){ x->s=x->lchild->s+x->rchild->s;}void Pushdown(ROOT &x,int m){if(x->a==1){x->lchild->a=x->rchild->a=1;x->lchild->s=m-(m>>1);x->rchild->s=m>>1;x->a=-1;}else if(!x->a){x->lchild->a=x->rchild->a=0;x->lchild->s=x->rchild->s=0;x->a=-1;}
}int Summation(ROOT &x,int l,int r,bool a){if(l<=x->l && x->r<=r){if(a) return x->r-x->l+1-x->s;else return x->s;}Pushdown(x,x->r-x->l+1);int m=(x->l+x->r)>>1,ret=0;if(l<=m) ret+=Summation(x->lchild,l,r,a);if(r>m) ret+=Summation(x->rchild,l,r,a);return ret;
}void Update(ROOT &x,int l,int r,bool a){if(l<=x->l && x->r<=r){if(a) x->a=1,x->s=x->r-x->l+1;else x->a=0,x->s=0;return;}Pushdown(x,x->r-x->l+1);int m=(x->l+x->r)>>1;if(l<=m) Update(x->lchild,l,r,a);if(mrchild,l,r,a);Pushup(x);
}int Query1(int x){int ret=0;for(int i=x;i!=-1;i=node[node[i].b].f)ret+=Summation(root,node[node[i].b].m,node[i].m,1);for(int i=x;i!=-1;i=node[node[i].b].f)Update(root,node[node[i].b].m,node[i].m,1);return ret;
}int Query2(int x){int ret=Summation(root,node[x].l,node[x].r,0);Update(root,node[x].l,node[x].r,0);return ret;
}int main(){scanf("%d",&N);for(int i=1,u;i){scanf("%d",&u);Insert(i,u),Insert(u,i);}DFS1(-1,0),cnt=0,DFS2(-1,0,0);Build(root,1,N);scanf("%d",&Q);for(int i=1,x;i<=Q;i++){scanf("%s %d",S,&x);if(S[0]=='i') printf("%d\n",Query1(x));else printf("%d\n",Query2(x));}return 0;
}

View Code