题意：给定一颗树，维护：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
【BZOJ4196 NOI2015 软件包管理器 树链剖分】View Code
