AGC033C 题解

这里树的直径 \(l\) 定义为两个有硬币的点的最长距离。

做一次操作后，树的直径一定会变短。

我们发现，如果在直径端点做操作，直径减一。

在非直径端点操作，直径减二。

于是变成了一个威佐夫博弈，但是要注意的是，在直径长度为 0,1,2 的时候，每次都只能让直径减一。

因为直径长度为 1，先手必败，所以变成了：

\(l\equiv 1\pmod 3\)，先手必败。

否则先手把 \(l\) 变成 \(l\equiv 1\pmod 3\)，变为后手，必胜。

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

const int N = 2e5 + 5;
int f[N], ans;
vector<int> e[N];
int n;

void dfs(int x, int fa)
{
    for(int i : e[x])
    {
        if(i == fa) continue;
        dfs(i, x);
        ans = max(ans, f[x] + f[i] + 1);
        f[x] = max(f[x], f[i] + 1);
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i ++)
    {
        int x, y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    cout << ((ans % 3 != 1) ? "First" : "Second");

    return 0;
}

看不出威佐夫博弈，可以 dp 求解。

设 \(f(i,j)\) 表示直径为 \(i\)，\(j\) 先手，谁获胜。

根据贪心，转移显然：

\(f(i,1)=\max(f(i-1,0),f(i-2,0))\\ f(i,0)=\min(f(i-1,1),f(i-2,1))\)

答案就是 \(f(l,0)\)。

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

const int N = 2e5 + 5;
int f[N], ans;
vector<int> e[N];
int n;

void dfs(int x, int fa)
{
    for(int i : e[x])
    {
        if(i == fa) continue;
        dfs(i, x);
        ans = max(ans, f[x] + f[i] + 1);
        f[x] = max(f[x], f[i] + 1);
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    int ff[N][2];
    memset(ff, -1, sizeof ff);
    ff[0][0] = 0, ff[0][1] = 1;
    ff[1][0] = 1, ff[1][1] = 0;
    ff[2][0] = 0, ff[2][1] = 1;
    for(int i = 3; i <= n; i ++)
    {
        ff[i][0] = min(ff[i - 1][1], ff[i - 2][1]);
        ff[i][1] = max(ff[i - 1][0], ff[i - 2][0]);
    }
    for(int i = 1; i < n; i ++)
    {
        int x, y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    cout << (!ff[ans][0] ? "First" : "Second");

    return 0;
}