题意:暂时并没有方法:树链剖分裸？解析:蛮水，不过承认自己现在代码能力太弱然而还是让我调过了啊啊啊太开心了述l棵有向树，所以只是从根节点到要安装的节点加值。比较裸的链剖。然后第二种询问呢，就是把一个整个子树删掉就好了，然后因为dfs序的性质，，每棵子树在线段树上是连续的。不过我写的线段树好烂跟140142学习了下姿势就好多了两种标记，一种是判断是否这个节点需要改值的标记，另一种是这个节点是清零还是赋1。然后就水过？代码:#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 100010#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1using namespace std;int n,cnt,tot,root;struct node{int from,to,val,next;}edge[N];int head[N];int size[N];int dep[N];int son[N];int top[N];int tim[N];int end[N];int num[N];int sum[N<<2];int col[N<<2];int col2[N<<2];int fa[N];void init(){memset(head,-1,sizeof(head));cnt=1;}void edgeadd(int from,int to){edge[cnt].to=to;edge[cnt].next=head[from];head[from]=cnt++;}void dfs1(int now){size[now]=1,son[now]=-1;for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==fa[now])continue;dep[to]=dep[now]+1;fa[to]=now;dfs1(to);size[now]+=size[to];if(son[now]==-1||size[son[now]]<size[to])son[now]=to;}}void dfs2(int now,int tp){top[now]=tp,tim[now]=++tot;if(son[now]!=-1)dfs2(son[now],tp);for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==fa[now]||to==son[now])continue;dfs2(to,to);}end[now]=tot;}void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushdown(int rt,int m){if(col[rt]){sum[rt<<1]=(m-(m>>1))*col2[rt];sum[rt<<1|1]=(m>>1)*col2[rt];col[rt<<1]=1,col[rt<<1|1]=1;col2[rt<<1]=col2[rt];col2[rt<<1|1]=col2[rt];col[rt]=0;}}void update(int L,int R,int l,int r,int rt,int jd){if(L<=l&&r<=R){col[rt]=1,col2[rt]=jd,sum[rt]=(r-l+1)*jd;return;}int mid=(l+r)>>1;pushdown(rt,r-l+1);if(L<=mid)update(L,R,lson,jd);if(R>mid)update(L,R,rson,jd);pushup(rt);}int query(int L,int R,int l,int r,int rt,int jd){if(L<=l&&r<=R){return sum[rt];}pushdown(rt,r-l+1);int ret=0;int mid=(l+r)>>1;if(L<=mid)ret+=query(L,R,lson,jd);if(R>mid)ret+=query(L,R,rson,jd);pushup(rt);return ret;}int install(int x,int y){int ans=0;ans=query(1,n,1,n,1,1);while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);int l=tim[top[x]],r=tim[x];update(l,r,1,n,1,1);x=fa[top[x]];}if(dep[x]>dep[y])swap(x,y);int l=tim[x],r=tim[y];update(l,r,1,n,1,1);ans=query(1,n,1,n,1,1)-ans;return ans;}char s[20];int main(){init();scanf(“%d”,&n);for(int i=2;i<=n;i++){int x;scanf(“%d”,&x);x++;edgeadd(x,i);}dfs1(1);dfs2(1,0);int q;scanf(“%d”,&q);while(q–){scanf(“%s”,s);int x;if(s[0]==’i’){scanf(“%d”,&x);x++;printf(“%d\n”,install(1,x));}else{scanf(“%d”,&x);x++;int l=tim[x],r=end[x];int ans=query(1,n,1,n,1,0);update(l,r,1,n,1,0);ans-=query(1,n,1,n,1,0);printf(“%d\n”,ans);}}}
伟人所达到并保持着的高处，并不是一飞就到的，
