2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest G Gangsters in Central City (LCA)
题意：
有一棵树，水源在根节点1，房子在叶子节点。有若干操作，操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水，可以通过切断边实现（如果某个叶子节点到根节点的路径上有一条边被切掉，那么就不能供水了。）对于每次操作后，问不给所有歹徒供水最少要切多少条边，并且问在切满足前面最小的情况下，最少使得多少个良民受影响。初始没有歹徒。
思路：
我们先考虑第一个问题。容易知道，假设与根相连的有k条边，那么最多只需要切k次，就切断了所有房子的水源。
也就是说，从最少切的次数角度的考虑，切与水源相连的边一定是最优的。
我们可以考虑把树根1去掉，这样得到k棵子树
然后可以预处理出，对于每个叶子节点，其非根的最远祖先是谁，也就是k棵子树的根节点都是谁。
那么对于每次出现歹徒，假设其非根的最远祖先是x,只需要切1-x这条边即可。
现在考虑第二个问题，在保证问题一最小的情况下，一个比较直观的想法是，我们尽量往低了切，也就是尽量往原理根的边上切，这样才能使收到影响的良民比较少。
容易想到，一个子树上该切的点是，所有被歹徒占领的坏点的LCA。这样可以使得受到影响的良民最少。
因为我们要得到受到影响的良民的数量，所以用siz[i]维护以i为根的子树的叶子数量，以及歹徒的数量。
这道题的关键结论是，：树上多个点的LCA，就是DFS序最小的和DFS序最大的这两个点的LCA"
这道题的关键结论是，：树上多个点的LCA，就是DFS序最小的和DFS序最大的这两个点的LCA"
这道题的关键结论是，：树上多个点的LCA，就是DFS序最小的和DFS序最大的这两个点的LCA"
因此这题就是写个LCA就可以了，切掉的坏点的dfs序可以用个set维护下。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月12日 星期四 17时06分57秒
4File Name :G.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int n,q;
36int val[N];
37vector < int > edge[N];
38int in[N];
39int E[2*N],R[2*N],dis[N],depth[2*N];
40int p;
41int fa[N];
42int dp[2*N][20];
43int siz[N]; //siz[i]表示以i为根的子树的叶子数量。
44int FA[N]; //将树根去掉之后，每棵子树最上面能到达的顶点。
45set<int>T[N];//T[i]表示与根节点直接连接的节点i 切掉的点的dfs序 id
46int a[N];
47void dfs( int u,int dep,int d,int pre)
48{
49 fa[u] = pre;
50 p++;
51 E[p] = u;
52 depth[p] = dep;
53 R[u] = p;
54 dis[u] = d;
55 int SIZ = edge[u].size();
56 if (SIZ==0) siz[u] = 1;
57 for ( int i = 0 ; i < SIZ ; i++)
58 {
59 int v = edge[u][i];
60 if (v==pre) continue;
61 if (u==1) FA[v] = v; //把树根去掉，原树分裂乘若干个子树
62 else FA[v] = FA[u];
63
64 dfs(v,dep+1,d+1,u);
65 siz[u] += siz[v];
66 p++;
67 E[p] = u;
68 depth[p] = dep;
69 }
70}
71int _min( int l,int r)
72{
73 if (depth[l] < depth[r]) return l;
74 return r;
75}
76void rmq_init()
77{
78 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i;
79
80 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++)
81 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++)
82 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
83}
84int rmq_min(int l,int r)
85{
86 if (l>r) swap(l,r);
87 int k = 0 ;
88 while (1<<(k+1)<=r-l+1) k++;
89 return _min(dp[l][k],dp[r-(1<<k)+1][k]);
90}
91int ans1=0,ans2=0;
92int main()
93{
94 #ifndef ONLINE_JUDGE
95 //freopen("./in.txt","r",stdin);
96
97 #endif
98 freopen("gangsters.in","r",stdin);
99 freopen("gangsters.out","w",stdout);
100 ms(a,0);
101 ms(siz,0);
102 scanf("%d %d",&n,&q);
103 for ( int i = 2 ; i <= n ; i++)
104 {
105 int x;
106 scanf("%d",&x);
107 // cout<<"x:"<<x<<endl;
108 edge[x].PB(i);
109 }
110 p = 0;
111 dfs(1,0,0,-1);
112 rmq_init();
113 while (q--)
114 {
115 char opt[3];
116 int x;
117 scanf("%s%d",opt,&x);
118 // cout<<opt<<" "<<x<<endl;
119 if (opt[0]=='+')
120 {
121 int fx = FA[x];
122 if (T[fx].size()==0) ++ans1;
123 T[fx].insert(R[x]);
124 ans2-=a[fx];//因为切掉了，先去掉之前的影响
125
126 int fi = *T[fx].begin();
127 int la = *T[fx].rbegin();
128 int LCA = E[rmq_min(fi,la)]; //尽量往低了切，才可能影响小。
129 // printf( "(LCA(%d %d)=%d,siz[LCA]=%d \n",R[fi],R[la],LCA,siz[LCA]);
130 a[fx] = siz[LCA] - T[fx].size();
131
132 ans2 += a[fx];//再考虑新的影响
133 // cout<<"ans2:"<<ans2<<endl;
134 }
135 else
136 {
137 int fx = FA[x];
138 if (T[fx].size()==1) ans1--;
139 T[fx].erase(R[x]);
140 ans2-=a[fx];
141 if (T[fx].size()!=0)
142 {
143 int fi = *T[fx].begin();
144 int la = *T[fx].rbegin();
145 int LCA = E[rmq_min(fi,la)];
146 a[fx] = siz[LCA] - T[fx].size();
147 // printf( "(LCA(%d %d)=%d\n",R[fi],R[la],LCA);
148 }
149 else a[fx] = 0;
150
151 ans2 +=a[fx];
152 }
153 printf("%d %d\n",ans1,ans2);
154 }
155
156 #ifndef ONLINE_JUDGE
157 fclose(stdin);
158 #endif
159 return 0;
160}