bzoj 4169: Lmc的游戏

题意：

给你一棵$n$个节点的树，上面有$m$个叶子。叶子有$1 \sim m$的权值，并且互不相同。两个人在树上玩游戏，一开始根节点有一个棋子，两人轮流把它移到当前的一个儿子上，最终移到叶子上，记这次游戏的结果是叶子的权值，先手想要尽可能大，后手想要尽可能小。现在你可以安排每个叶子的权值，问游戏的结果最大和最小是多少。

题解：

如果确定了叶子的权值，那么最终的结果可以用简单的树形DP求出来，就是$f_x$表示$x$这棵子树的结果，然后如果$x$是先手动，就找最大的走过去，后手就找最小的。观察一下，我们发现一棵子树的结果只和它里面的叶子的权值的相对大小有关，所以我们可以设$f_x$表示$x$的结果是第几大的。转移很简单，具体看代码吧。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, root, num = 0, fst[200010], dep[200010], f[200010], cnt[200010];
bool tf[200010];
struct edge
{
    int x, y, n;
} e[200010];

void ins(int x, int y)
{
    e[++num] = {x, y, fst[x]};
    fst[x] = num;
}
void pre(int x)
{
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        dep[y] = dep[x] + 1;
        pre(y);
        cnt[x] += cnt[y];
    }
    if (!cnt[x]) cnt[x] = 1;
}
int get_mx(int x)
{
    if (dep[x] & 1) f[x] = cnt[x];
    else f[x] = 0;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        get_mx(y);
        if (dep[x] & 1) // 先手
            f[x] = min(f[x], f[y]);
        else // 后手
            f[x] += f[y];
    }
    if (!fst[x]) f[x] = 1;
    return f[x];
}
int get_mn(int x)
{
    if (dep[x] & 1) f[x] = 1;
    else f[x] = 0;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        get_mn(y);
        if (dep[x] & 1)
            f[x] += f[y] - 1;
        else
            f[x] = max(f[x], f[y] + cnt[x] - cnt[y]);
    }
    if (!fst[x]) f[x] = 1;
    return f[x];
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ins(x, y);
        tf[y] = 1;
    }
    for (int i = 1; i <= n; i++) if (!tf[i]) { root = i; break; }
    dep[root] = 1;
    pre(root);
    // printf("%d\n", cnt[root]);
    printf("%d %d\n", cnt[root] - get_mx(root) + 1, cnt[root] - get_mn(root) + 1);
}