http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=847&page=show_problem&problem=3661

记父节点为u,子节点为v。
若选了u,则所有子节点都不能选,dp[u][1]=sum{dp[v][0]}
若不选,则子节点可选可不选,dp[u][0]=sum{max(dp[v][0],dp[v][1])}
对于方案是否唯一,转移时判断下就行,详见代码。

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = 205;

vector<int> g[mx];
map<string, int> m;
char s[105];
int dp[mx][2];
bool uni[mx][2];

inline int id()
{
    SS(s);
    return m[s] ? m[s] : m[s] = m.size();
}

inline bool ok(int v)
{
    return dp[v][0] != dp[v][1] ? uni[v][dp[v][0] < dp[v][1]] : false;
}

int f(int u, bool choose)
{
    dp[u][choose] = choose;
    uni[u][choose] = true;
    int i, v;
    For(i, g[u].size())
    {
        v = g[u][i];
        if (choose)
        {
            dp[u][1] += f(v, 0);
            if (!uni[v][0]) uni[u][1] = false;
        }
        else
        {
            dp[u][0] += max(f(v, 0), f(v, 1));
            if (!ok(v)) uni[u][0] = false;
        }
    }
    return dp[u][choose];
}

int main()
{
    int n, i, x, y;
    while (SI(n), n)
    {
        Forr(i, 1, n + 1) g[i].clear();
        m.clear();
        id();
        while (--n) x = id(), y = id(), g[y].PB(x);
        printf("%d ", max(f(1, 0), f(1, 1)));
        puts(ok(1) ? "Yes" : "No");
    }
    return 0;
}

Comments

comments powered by Disqus