题意： 一棵树1为根结点，点1 是水源，其它叶子结点是村庄。 q 个询问，每次询问有强盗入侵或离开某个村庄，要求输出两个数 ans1,ans2。 ans1表示最少要切断多少条边，使得强盗入侵的村庄与点1 不连通； ans2表示在确定了 ans1 的基础上，最少有多少个村庄没有被强盗入侵但又不与点1 连通。
tags： 把点1 的所有儿子结点所拥有的子树单独圈出来，每次更新就在这个村庄所在的儿子结点的子树上操作即可。 按 dfs 序标出，每次只要看这个儿子标点上 dfs 序最小和最大的点。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 100005; int n, q, cnt, id[N], in[N], pi[N], Size[N]; struct Edge { int to, next; } e[N<<2]; vector< int > Son; set< int > se[N]; int tot, head[N]; void Addedge(int u, int v) { e[tot] = (Edge){ v, head[u] }; head[u]=tot++; } int dep[N], p[N][30]; void dfslca(int u, int fa) { dep[u]=dep[fa]+1, p[u][0]=fa; for(int i=head[u], to; to=e[i].to, ~i; i=e[i].next) if(to!=fa) dfslca(to, u); } void Initlca() { mes(p, -1); mes(dep, 0); dep[0]=-1; dfslca(1, 0); for(int j=1; (1<<j)<=n; ++j) rep(i,1,n) if(p[i][j-1]!=-1) p[i][j] = p[p[i][j-1]][j-1]; } int Lca(int a, int b) { int i, j; if(dep[a] < dep[b]) swap(a, b); for(i=0; (1<<i)<=dep[a]; ++i) ; --i; for(j=i; j>=0; --j) if(dep[a]-(1<<j) >= dep[b]) a = p[a][j]; if(a==b) return a; for(j=i; j>=0; --j) if(p[a][j]!=-1 && p[a][j]!=p[b][j]) a=p[a][j], b=p[b][j]; return p[a][0]; } int dfs(int u, int fa, int son_id) { if(fa==1) { Son.PB(u); son_id = Son.size()-1; } in[u]=++cnt, id[cnt]=u, pi[u]=son_id; bool flag = true; for(int i=head[u], to; to=e[i].to, ~i; i=e[i].next) if(to!=fa) Size[u] += dfs(to, u, son_id), flag=false; return Size[u] += (flag==true); } int get(int x) { if(se[x].size()==0) return 0; int l = *se[x].begin(), r = *(--se[x].end()); l = id[l], r = id[r]; int lca = Lca(l, r); return Size[lca] - se[x].size(); } int main() { freopen("gangsters.in","r",stdin); freopen("gangsters.out","w",stdout); mes(head, -1); scanf("%d%d", &n, &q); int pii; rep(i,2,n) { scanf("%d", &pii); Addedge(pii, i); Addedge(i, pii); } Initlca(); Son.PB(0); dfs(1, 0, 0); int ans1=0, ans2=0, v, tmp1, tmp2; char ch; while(q--) { scanf("%*c%c %d", &ch, &v); tmp1 = get(pi[v]); if(ch=='+') { if(se[pi[v]].size()==0) ++ans1; se[pi[v]].insert(in[v]); } else { if(se[pi[v]].size()==1) --ans1; se[pi[v]].erase(in[v]); } tmp2 = get(pi[v]); ans2 = ans2 - tmp1 + tmp2; printf("%d %d ", ans1, ans2); } return 0; } /* 7 6 1 2 1 3 3 3 + 4 + 5 + 6 + 7 - 6 - 5 */