题意：给你一棵树 1为根节点（水源），叶子节点为村民 现在有一些小偷入侵了村庄
我们现在想切断水源 使得小偷渴死 每个小偷有一个入侵和离开的时间
求 我们最少需要切断多少次以及被断水影响到的村民个数
思路：学习了付队的博客
我们以水源连的边作为子树的根（暂记做k），求得每个子树的叶子节点个数
我们用set记录 以k为根节点的子树的小偷 的dfs序 因为我们要尽量少删边 直接求dfs序最小和最大的lca即可
同时更新每次切点的sz和子树的小偷个数
#include<bits/stdc++.h> #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pb push_back #define P pair<int,int> #define INF 1e18 using namespace std; const int maxn = 200005; vector<int> G[maxn]; set<int> s[maxn]; int dfn[maxn],pos[maxn],dep[maxn],sz[maxn],son[maxn],tmp[maxn]; int f[maxn],fa[maxn][20],times,cut[maxn],num[maxn]; void dfs(int u,int fa,int two){ //two用来存水源下的边 dfn[u]=++times; pos[times]=u; dep[u]=dep[fa]+1; if(dep[u]==2) two=u; if(two) f[u]=two; for(auto x:G[u]){ if(x==fa) continue; dfs(x,u,two); son[u]+=sz[x]; } if(!son[u]) sz[u]=1; else sz[u]=son[u]; } int Lca(int u,int v){ if(dep[u]<dep[v]) swap(u,v); for(int i=19;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=18;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int main(){ freopen("gangsters.in","r",stdin); freopen("gangsters.out","w",stdout); int n,q; scanf("%d %d",&n,&q); for(int i=2;i<=n;i++){ scanf("%d",&fa[i][0]); G[fa[i][0]].push_back(i); } for(int i=1;i<=19;i++) for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1]; dfs(1,0,0); char op[5]; int x; int ans1=0,ans2=0; while(q--){ scanf("%s %d",op,&x); int t=f[x]; if(op[0]=='+'){ if(s[t].empty()) ans1++; else ans2-=tmp[t]; s[t].insert(dfn[x]); int lca=Lca(pos[*s[t].begin()],pos[*s[t].rbegin()]); cut[t]=lca; num[t]++; tmp[t]=sz[cut[t]]-num[t]; ans2+=tmp[t]; }else { ans2-=tmp[t];tmp[t]=0; s[t].erase(dfn[x]);num[t]--; if(s[t].empty()) ans1--; else { int lca=Lca(pos[*s[t].begin()],pos[*s[t].rbegin()]); cut[t]=lca; tmp[t]=sz[cut[t]]-num[t]; ans2+=tmp[t]; } } printf("%d %d ",ans1,ans2); } return 0; }