题目背景是一个安装与卸载软件的系统，软件之间关系是一棵树，以0为根节点。当你安装一个软件时需要先安装它的所有祖先，卸载时则要先卸载整个子树。对每一次操作询问改变状态的软件数目。
思路：dfs序做树剖，用线段树维护数据。
#include<iostream> #include<vector> #include<stdio.h> #define ls (id*2) #define rs (id*2+1) using namespace std; vector<int> lin[]; int in[],size[],fa[],top[],n,num,ans; struct node { int val; int lazy; }t[*4]; int abs(int a) { return a>=0?a:-a; } void push_down(int id,int l,int mid,int r) { if (t[id].lazy==-1)return; t[ls].lazy=t[id].lazy; t[rs].lazy=t[id].lazy; t[ls].val=(mid-l+1)*t[id].lazy; t[rs].val=(r-mid)*t[id].lazy; t[id].lazy=-1; } void push_up(int id) { t[id].val=t[ls].val+t[rs].val; } void build(int id,int l,int r) { if(l==r) { t[id].val=0; t[id].lazy=-1;//改成-1！切记！ return; } int mid=(l+r)/2; build(ls,l,mid); build(rs,mid+1,r); push_up(id); } void insert(int id,int l,int r,int L,int R,int V) { if(r<L||l>R) return; if(r<=R && l>=L) { ans+=abs(V*(r-l+1)-t[id].val); t[id].val=V*(r-l+1); t[id].lazy=V; return; } int mid=(l+r)/2; push_down(id,l,mid,r); insert(ls,l,mid,L,R,V); insert(rs,mid+1,r,L,R,V); push_up(id); } void dfs1(int x,int pre) { in[x]=++num; fa[x]=pre; for (int i=0;i<lin[x].size();i++) { int nex=lin[x][i]; if (nex==pre) continue; dfs1(nex,x); } size[x]=num-in[x]+1;//必须+1，否则dfs2中判断叶子节点很麻烦。 } void dfs2(int x,int t) { in[x]=++num; top[x]=t; if (size[x]==1) return;//叶子节点直接返回，否则会死循环(不能用size[x]=0做!) int msize=0,heavy=0;//都要赋初始值！ for (int i=0;i<lin[x].size();i++) { int nex=lin[x][i]; if (nex==fa[x]) continue; if (size[nex]>msize) { msize=size[nex]; heavy=nex; } } dfs2(heavy,t);//先走重儿子，其他随意 for (int i=0;i<lin[x].size();i++) { int nex=lin[x][i]; if (nex==fa[x] || nex==heavy) continue; dfs2(nex,nex); } } int main() { cin>>n; for (int i=1;i<n;i++) { int a; cin>>a;//编号都+1，防止爆线段树 lin[a+1].push_back(i+1); lin[i+1].push_back(a+1); } num=0; dfs1(1,0); num=0; dfs2(1,1); int q; cin>>q; char s[15]; while (q--) { int a; scanf("%s",s);//一定不要用cin！！！！T了半个小时... scanf("%d",&a); a++; if (s[0]=='i') { ans=0; while (a!=0) { insert(1,1,n,in[top[a]],in[a],1); a=fa[top[a]]; } printf("%d\n",ans); } if (s[0]=='u') { ans=0; insert(1,1,n,in[a],in[a]+size[a]-1,0); printf("%d\n",ans); } } }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/86366.html