可能洛谷上的题目描述更友好一些：https://www.luogu.com.cn/problem/P2146
这个题和不同的树链剖分有一点不同，首先建图时考虑单向边
其次利用 lazy 操作，分别计算安装 x 时需要在安装多少，因为可能不在同一条链上，所以利用述链剖分
但是删除 x 时，一定在一条链上，所以直接在线段树上操作即可
const int N=1e5+5;int n,m,t;int i,j,k;int a[N];vector<int> G[N<<1];int sz[N],son[N],fa[N],dep[N];void dfs1(int u,int f)
{sz[u]=1;dep[u]=dep[f]+1;fa[u]=f;int len=G[u].size();for(int i=0;i<len;i++){int v=G[u][i];if(v==f) continue;dfs1(v,u);sz[u]+=sz[v];if(sz[son[u]]<sz[v]) son[u]=v;}
}int top[N],tree[N],id[N],tot=0;
//id : dfs序 tree : 线段树序void dfs2(int u,int f)
{top[u]=f;id[u]=++tot;tree[tot]=u;if(!son[u]) return ;dfs2(son[u],f);int len=G[u].size();for(int i=0;i<len;i++){int v=G[u][i];if(v==fa[u] || v==son[u]) continue;dfs2(v,v);}
}struct Node{int l,r;ll sum;ll lazy;void update(ll x){sum = 1ll*(r-l+1)*x;lazy = x;}}node[N<<2];void push_up(int id)
{node[id].sum=node[id<<1].sum+node[id<<1|1].sum;
}void push_down(int id)
{ll x=node[id].lazy;if(~x){node[id<<1].update(x);node[id<<1|1].update(x);node[id].lazy=-1;}
}void build(int l,int r,int id)
{node[id].l=l,node[id].r=r;if(l==r){node[id].lazy=-1;} else{int mid=l+r>>1;build(l,mid,id<<1);build(mid+1,r,id<<1|1);}
}void update(int l,int r,int id,ll val)
{int L=node[id].l,R=node[id].r;if(L>=l && r>=R){node[id].update(val);} else{int mid=L+R>>1;push_down(id);if(mid>=l) update(l,r,id<<1,val);if(r>=mid+1) update(l,r,id<<1|1,val);push_up(id);}
}#define nx top[x]
#define ny top[y]void Other_update(int x,int y)
{while(nx!=ny){if(dep[nx]<dep[ny]) swap(x,y);update(id[nx],id[x],1,1);x=fa[nx];}if(dep[x]>dep[y]) swap(x,y);return update(id[x],id[y],1,1);
}int main()
{//IOS;while(~sd(n)){for(i=0;i<N*2;i++) G[i].clear();int x;for(i=2;i<=n;i++){ //从 1 开始建图sd(x); x++;G[x].pb(i);}dfs1(1,0); dfs2(1,1);build(1,n,1);char s[10];rush(){ss(s);sd(x); x++;int cur=node[1].sum;if(s[0]=='i'){Other_update(1,x);pd(node[1].sum-cur);} else if(s[0]=='u'){update(id[x],id[x]+sz[x]-1,1,0);pd(cur-node[1].sum);}}}//PAUSE;return 0;
}