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维护下。
/* ***********************************************
Author :111qqz
Created Time :2017年10月12日 星期四 17时06分57秒
File Name :G.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n,q;
8int val[N];
9vector < int > edge[N];
10int in[N];
11int E[2*N],R[2*N],dis[N],depth[2*N];
12int p;
13int fa[N];
14int dp[2*N][20];
15int siz[N]; //siz[i]表示以i为根的子树的叶子数量。
16int FA[N]; //将树根去掉之后，每棵子树最上面能到达的顶点。
17set<int>T[N];//T[i]表示与根节点直接连接的节点i 切掉的点的dfs序 id
18int a[N];
19void dfs( int u,int dep,int d,int pre)
20{
21 fa[u] = pre;
22 p++;
23 E[p] = u;
24 depth[p] = dep;
25 R[u] = p;
26 dis[u] = d;
27 int SIZ = edge[u].size();
28 if (SIZ==0) siz[u] = 1;
29 for ( int i = 0 ; i < SIZ ; i++)
30 {
31 int v = edge[u][i];
32 if (v==pre) continue;
33 if (u==1) FA[v] = v; //把树根去掉，原树分裂乘若干个子树
34 else FA[v] = FA[u];
1 dfs(v,dep+1,d+1,u);
2 siz[u] += siz[v];
3 p++;
4 E[p] = u;
5 depth[p] = dep;
6 }
7}
8int _min( int l,int r)
9{
10 if (depth[l] < depth[r]) return l;
11 return r;
12}
13void rmq_init()
14{
15 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i;
1 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++)
2 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++)
3 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
4}
5int rmq_min(int l,int r)
6{
7 if (l>r) swap(l,r);
8 int k = 0 ;
9 while (1<<(k+1)<=r-l+1) k++;
10 return _min(dp[l][k],dp[r-(1<<k)+1][k]);
11}
12int ans1=0,ans2=0;
13int main()
14{
15 #ifndef ONLINE_JUDGE
16 //freopen("./in.txt","r",stdin);
1 #endif
2 freopen("gangsters.in","r",stdin);
3 freopen("gangsters.out","w",stdout);
4 ms(a,0);
5 ms(siz,0);
6 scanf("%d %d",&n,&q);
7 for ( int i = 2 ; i <= n ; i++)
8 {
9 int x;
10 scanf("%d",&x);
11 // cout<<"x:"<<x<<endl;
12 edge[x].PB(i);
13 }
14 p = 0;
15 dfs(1,0,0,-1);
16 rmq_init();
17 while (q--)
18 {
19 char opt[3];
20 int x;
21 scanf("%s%d",opt,&x);
22 // cout<<opt<<" "<<x<<endl;
23 if (opt[0]=='+')
24 {
25 int fx = FA[x];
26 if (T[fx].size()==0) ++ans1;
27 T[fx].insert(R[x]);
28 ans2-=a[fx];//因为切掉了，先去掉之前的影响
1 int fi = *T[fx].begin();
2 int la = *T[fx].rbegin();
3 int LCA = E[rmq_min(fi,la)]; //尽量往低了切，才可能影响小。
4 // printf( "(LCA(%d %d)=%d,siz[LCA]=%d \n",R[fi],R[la],LCA,siz[LCA]);
5 a[fx] = siz[LCA] - T[fx].size();
1 ans2 += a[fx];//再考虑新的影响
2 // cout<<"ans2:"<<ans2<<endl;
3 }
4 else
5 {
6 int fx = FA[x];
7 if (T[fx].size()==1) ans1--;
8 T[fx].erase(R[x]);
9 ans2-=a[fx];
10 if (T[fx].size()!=0)
11 {
12 int fi = *T[fx].begin();
13 int la = *T[fx].rbegin();
14 int LCA = E[rmq_min(fi,la)];
15 a[fx] = siz[LCA] - T[fx].size();
16 // printf( "(LCA(%d %d)=%d\n",R[fi],R[la],LCA);
17 }
18 else a[fx] = 0;
1 ans2 +=a[fx];
2 }
3 printf("%d %d\n",ans1,ans2);
4 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}