洛谷 P3554 [POI2013]LUK-Triumphal arch

给一颗树，1号节点已经被染黑，其余是白的，两个人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步，如果B能走到A没染的节点则B胜，否则当A染完全部的点时，A胜。求能让A获胜的最小的k

首先我们直接二分

然后考虑怎么验证答案

对于B而言，一定是只能从根往叶子节点走的，因为如果回到父亲就相当于白走了一次，从而多让A染了色

而对于A来说，首先要染的一定是B当前所在的点的所有儿子节点

于是我们可以设(f_u)表示以u为根的子树中，u点不染色会多出来几个点没被染色

这个没被染色的意思是在B在u点时，B胜后u这棵树有多少个点没被染色，或者B是输的

理解了状态就能写出转移方程了

[f_u=max(0,sum_{vin son(u)}f_v + to_u-x) ]

其中x是二分的答案，(to_u)是u的儿子数

简单来说就是这棵子树中如果有没染的节点也就是(f_v)，那么这次就要染上。0表示B是输的。这样就比较好理解了QAQ

当然，在二分的时候，我们还可以确定出一个下界也就是(to_1)

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
const int N = 3e5;
using namespace std;
int n,ans,f[N + 5],to[N + 5];
vector <int> d[N + 5];
void dfs(int u,int fa,int x)
{
    vector <int>::iterator it;
    int sum = 0;
    for (it = d[u].begin();it != d[u].end();it++)
    {
        int v = (*it);
        if (v == fa)
            continue;
        dfs(v,u,x);
        sum += f[v];
    }
    f[u] = max(0,to[u] + sum - x);
}
int check(int x)
{
    dfs(1,0,x);
    return f[1] == 0;
}
int main()
{
    scanf("%d",&n);
    int u,v;
    for (int i = 2;i <= n;i++)
        to[i] = -1;
    for (int i = 1;i < n;i++)
    {
        scanf("%d%d",&u,&v);
        d[u].push_back(v);
        d[v].push_back(u);
        to[u]++;
        to[v]++;
    }
    vector <int>::iterator it;
    int l = to[1],r = n,mid;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(mid))
            r = mid - 1,ans = mid;
        else
            l = mid + 1;
    }
    cout<<ans<<endl;
    return 0;
}