AtCoder Regular Contest 112 C - DFS Game

树上DP,考虑到先后手变化只和子树大小有关,因为每条边走两次,点走一次;

令dp[u]为拿u点coin的情况下对于整个子树,两人的硬币差会是多少,那么对于另一方而言,先选择不交换先后手并且对自己更好的子树(即dp[v] < 0),然后和另一方轮流选择子树,两方都会选择dp[v]尽可能最小的让自己的尽可能的多,最后一个人*就要选择之前那些不交换先后手并且对自己不好的子树。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int fa[N], dp[N], sz[N];
vector < int > edge[N];
void dfs(int u) {
    int sum = 0; sz[u] = dp[u] = 1;
    vector < int > vt;
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i];
        dfs(v);
        sz[u] += sz[v];
        if (sz[v] & 1)    vt.push_back(dp[v]);
        else {    
            if (dp[v] < 0)    dp[u] += dp[v];
            else    sum += dp[v];
        }
    }
    sort(vt.begin(), vt.end());
    vt.push_back(sum);
    for (int i = 0; i < vt.size(); i++) {
        if (i & 1)    dp[u] -= vt[i];
        else    dp[u] += vt[i];
    }
    return ;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int x; scanf("%d", &x);
        edge[x].push_back(i);
    }
    dfs(1);
    printf("%d\n", (dp[1] + n) / 2);
    return 0;
}

 

上一篇:COCI 2020/2021 CONTEST #2 解题报告


下一篇:Sumitomo Mitsui Trust Bank Programming Contest 2019