原题大意

首先看一下什么是最小支配集：

http://www.cnblogs.com/Ash-ly/p/5775934.html

本题中也类似，给一棵树，n个人编号0~n-1，0为CEO，其余每个人都有一个直接上司，现在问题是有些人比较懒（用0表示），所以这些人需要去参加会议（估计是批斗大会什么的），当这些人回来后，他们就变得勤奋努力，认真踏实……，而且带动与他相连的结点也进入一样的状态（如果本来就是1，就没有什么变化，否则由0变成1），现在问最少喊几个人去开会，能使所有人变得不懒惰。（注意！CEO永远不会懒惰，且没有上司）

算法分析

本题是一个很好的模版题，填补了我对于最小支配集的空缺，官方题解也很详细。

最小支配集的算法：

http://www.cnblogs.com/Ash-ly/p/5783877.html

官方题解：

https://www.hackerrank.com/contests/rookierank-3/challenges/culture-conference/editorial

程序代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 100000000;
const int maxn = 1e6+5;
int n;
vector<int> edge[maxn];
int b[maxn];
int dp1[maxn];//支配
int dp2[maxn];//被子支配
int dp3[maxn];//被父支配
int main() {
 freopen("input.txt", "r" ,stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n - 1; i++){
        int t;
        cin >> t >> b[i];
        edge[t].push_back(i);
    }
    b[0] = 1;//CEO永远不懒惰
    for(int i = n-1; i >= 0; i--){
        dp1[i] = 1;
        if(edge[i].size() == 0){
            dp1[i] = 1;
            dp2[i] = (b[i] == 1)? 0 : INF;
            dp3[i] = 0;
            continue;
        }
        int cnt = 0;
        bool fg = false;//是否存在一个dp1<=dp2
        for(int p : edge[i]){
            if(dp1[p] <= dp2[p]) {fg = true;break;}
        }
        if(!fg)
        {
            for(int p : edge[i]){
                cnt+=dp2[p];
            }
            if(b[i] == 0)dp2[i] = INF;//这里的dp2[i]初始很大，不同于fg==true和b[i]==1时的。
        }

        for(int p : edge[i]){
            dp3[i]+=min(dp1[p], dp2[p]);
            if(b[i] == 1){
                dp2[i] += min(dp1[p] , dp2[p]);
                dp1[i] += min(dp1[p], min(dp2[p], dp3[p]));
            }
            else{
                dp1[i] += min(dp1[p], min(dp2[p], dp3[p]));
                if(fg == true){
                    dp2[i] += min(dp1[p], dp2[p]);
                }
                else{
                    dp2[i] = min(dp2[i], cnt - dp2[p] + dp1[p]);
                }

            }
        }
    }
    cout << min(dp1[0],dp2[0])<<endl;//CEO不会被父节点支配
    return 0;
}