UVA 1220 Party at Hali-Bula (树形DP)

求一棵数的最大独立集结点个数并判断方案是否唯一。

dp[i][j]表示以i为根的子树的最大独立集，j的取值为选和不选。

决策：

当选择i时，就不能选择它的子结点。

当不选i时，它的子结点可选可不选。

判断唯一性：当选择的某个子节点方案不唯一，父节点的方案就不唯一，或者某个子节点选或不选方案数一样。

转移顺序：按照拓扑序转移或dfs都可以。

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

const int pick = ;

const int drop = ;

int d[maxn][];

bool f[maxn][];// NotUnique?

int fa[maxn];

int deg[maxn];

int n;

void topo()

{

    queue<int> q;

    for(int i = ; i < n; i++){

        d[i][pick] = ;

        d[i][drop] = ;

        f[i][pick] = f[i][drop] = ;

        if(deg[i] == ){

            q.push(i);

        }

    }

    while(q.size()){

        int u = q.front(); q.pop();

        int p = fa[u];

        int &a = d[u][drop], &b = d[u][pick];

        d[p][pick] += a;

        f[p][pick] |= f[u][drop];

        if(a>b){

            d[p][drop] += a;

            f[p][drop] |= f[u][drop];

        }else {

            d[p][drop] += b;

            f[p][drop] |= a == b || f[u][pick];

        }

        deg[p]--;

        if(deg[p] == ) {

            q.push(p);

        }

    }

}

#define MP make_pair

#define PB push_back

#define fi first

#define se second

map<string,int> idx;

int idx_cnt;

int ID(string &x)

{

    map<string,int>::iterator it = idx.find(x);

    if(it != idx.end()) return it->se;

    idx.insert(MP(x,idx_cnt));

    return idx_cnt++;

}

string name;

const int root = ;

bool read()

{

    scanf("%d",&n);

    if(n == ) return false;

    idx.clear();

    cin>>name;

    idx.insert(MP(name,root));

    idx_cnt = ;

    fill(deg,deg+n,);

    for(int i = ; i < n; i++){

        cin>>name;

        int v = ID(name);

        cin>>name;

        int p = ID(name);

        fa[v] = p;

        deg[p]++;

    }

    return true;

}

int main()

{

    //freopen("in.txt","r",stdin);

    fa[root] = -;

    while(read()){

        topo();

        int k = d[root][pick]>d[root][drop]?pick:drop;

        bool flag = d[root][k] != d[root][k^] && !f[root][k];

        printf("%d ",d[root][k]);

        if(flag) puts("Yes");

        else puts("No");

    }

    return ;

}