题意：
树的根节点为水源，编号为 1 。给定编号为 2, 3, 4, …, n 的点的父节点。已知只有叶子节点都是房子。
有 q 个操作，每个操作可以是下列两者之一：
+ v，表示编号为 v 的房子被歹徒占领。- v，表示歹徒退出编号为 v 的房子。
初始所有房子都没有歹徒。对于每次变化后，要求删除最少的边，使得所有有歹徒的房子均无法与水源连通；同时，在此基础上要求受影响的普通房子数量最少。
题解：
首先对树的根节点的子树分类，那么实际上最多删除的边就是子树个数。
对于每个子树，如果要求受影响的普通房子数量最少，那么其实就是求所有歹徒的房子的lca。
求这个lca，可以利用dfs序，选dfs序最小的那个结点和最大的那个结点求出的lca就是所有结点的lca（这个可以用set维护）
然后用树状数组维护有多少普通房子受到影响即可。
#include <iostream> #include <cstdio> #include <vector> #include <set> #define fi first #define se second using namespace std; typedef pair<int, int> PII; const int maxn = 1e5 + 100; int c[maxn*8], F[maxn][2]; int deep[maxn], p[maxn][30], col[maxn]; vector<int> G[maxn]; set<PII> S[maxn][2]; int n, x, tot, q; char str[10]; PII ans; void Modify(int x, int s){ for(; x <= 2*n; x += x&(-x)) c[x] += s; } int Query(int y){ if(y <= 0) return 0; int ans = 0; for(int x = y; x; x -= x&(-x)) ans += c[x]; return ans; } int query(int x, int y) { return Query(y) - Query(x-1); } int lca(int u, int v) { if(deep[u] > deep[v]) swap(u, v); for(int i = 20; i >= 0; i--) if(deep[p[v][i]] >= deep[u]) v = p[v][i]; if(u == v) return u; for(int i = 20; i >= 0; i--) if(p[v][i] != p[u][i]) u = p[u][i], v = p[v][i]; return p[u][0]; } void dfs(int x, int fa, int d, int lab){ p[x][0] = fa; deep[x] = d; col[x] = lab; F[x][0] = ++tot; for(auto to : G[x]){ if(to == fa) continue; dfs(to, x, d+1, lab); } F[x][1] = ++tot; if(G[x].size() == 0) { Modify(F[x][0], 1); Modify(F[x][1], 1); } } void lca_pre(){ for(int j = 1; j <= 20; j++) for(int i = 1; i <= n; i++) p[i][j] = p[p[i][j-1]][j-1]; } int main() { freopen("gangsters.in", "r", stdin); freopen("gangsters.out", "w", stdout); cin>>n>>q; for(int i = 1; i < n; i++){ scanf("%d", &x); G[x].push_back(i+1); } int coln = G[1].size(); for(int i = 0; i < G[1].size(); i++) dfs(G[1][i], 1, 1, i+1); lca_pre(); int u, v, uv; while(q--){ cin>>str; if(str[0] == '+'){ scanf("%d", &x); if(S[col[x]][0].size() == 0) ans.fi++; if(S[col[x]][0].size() > 0){ u = (*S[col[x]][0].begin()).se; v = (*--S[col[x]][1].end()).se; uv = lca(u, v); if(G[uv].size() != 0) ans.se -= query(F[uv][0], F[uv][1])/2; } S[col[x]][0].insert({F[x][0], x}); S[col[x]][1].insert({F[x][1], x}); Modify(F[x][0], -1); Modify(F[x][1], -1); u = (*S[col[x]][0].begin()).se; v = (*--S[col[x]][1].end()).se; uv = lca(u, v); if(G[uv].size() != 0) ans.se += query(F[uv][0], F[uv][1])/2; printf("%d %d ", ans.fi, ans.se); } else { scanf("%d", &x); if(S[col[x]][0].size() == 1) ans.fi--; u = (*S[col[x]][0].begin()).se, v = (*--S[col[x]][1].end()).se; uv = lca(u, v); if(G[uv].size() != 0) ans.se -= query(F[uv][0], F[uv][1])/2; S[col[x]][0].erase({F[x][0], x}); S[col[x]][1].erase({F[x][1], x}); Modify(F[x][0], 1); Modify(F[x][1], 1); if(S[col[x]][0].size() > 0){ u = (*S[col[x]][0].begin()).se, v = (*--S[col[x]][1].end()).se; uv = lca(u, v); if(G[uv].size() != 0) ans.se += query(F[uv][0], F[uv][1])/2; } printf("%d %d ", ans.fi, ans.se); } } return 0; }