题意：

树的根节点为水源，编号为 1 。给定编号为 2, 3, 4, …, n 的点的父节点。已知只有叶子节点都是房子。

有 q 个操作，每个操作可以是下列两者之一：

1. + v ，表示编号为 v 的房子被歹徒占领。
2. - v ，表示歹徒退出编号为 v 的房子。

初始所有房子都没有歹徒。对于每次变化后，要求删除最少的边，使得所有有歹徒的房子均无法与水源连通；同时，在此基础上要求受影响的普通房子数量最少。

 

题解：

首先对树的根节点的子树分类，那么实际上最多删除的边就是子树个数。

对于每个子树，如果要求受影响的普通房子数量最少，那么其实就是求所有歹徒的房子的lca。

求这个lca，可以利用dfs序，选dfs序最小的那个结点和最大的那个结点求出的lca就是所有结点的lca（这个可以用set维护）

然后用树状数组维护有多少普通房子受到影响即可。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define fi first#define se secondusing namespace std;typedef pair
         
           PII;const int maxn = 1e5 + 100;int c[maxn*8], F[maxn][2];int deep[maxn], p[maxn][30], col[maxn];vector
          
            G[maxn];set
           
             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\n", 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\n", ans.fi, ans.se); } } return 0;}