看到这道题,是个博弈论,没见过树上的,于是想到在数列里的博弈论,又联想到树的特殊形式————链。
于是我们来讨论一下链的情况(对于没有硬币的点,我们就视为它被删掉了):
发现若是选择两端的点,顶点数会减一;若是选择中间的点,顶点数会减二。
现在我们站在链的角度来思考在树上选择的情况,一颗树可以看成一条链且在某些顶点上有分支的图。我们再来以这种方式来选点找找规律,发现树上的点删着删着最后总会变成一条链,且这条链是最长链的子链,于是我们把看这棵树的形式转换为其最长链(直径)且在某些顶点上有分支的图:
通过手玩这个例子后发现,我们若是选最长链两端的点,最长链顶点数会减一;若是选择非最长链两端的点,最长链顶点数会减二,其余的分支会因为持续的选点而被删完。
所以发现,在树上的问题被我们转化成了在链上的问题,妙哉!
讨论完了删点的变化情况,我们再来讨论一下必胜条件:若最长链上有 \(i-1\) 和 \(i-2\) 个点时均必胜,则最长链上有 \(i\) 个点时必败,否则必胜,特殊的,若最长链上有 \(1\) 个点时必胜,有 \(2\) 个点时必败。
打表发现用树的最长链上点的个数 \(\mod 3\) ,若等于 2 后手胜,否则先手胜。
Code:
#include<iostream> #include<algorithm> using namespace std; const int N = 2e5 + 5; int n, x, y, fir, sec; int la[N], en[N << 1], ne[N << 1], idx; void add(int x, int y) { en[ ++ idx] = y; ne[idx] = la[x]; la[x] = idx; } void dfs(int u, int f, int step) { for (int i = la[u]; i; i = ne[i]) { int v = en[i]; if(v == f) continue; if(fir < step) fir = step, sec = v; dfs(v, u, step + 1); } } int main(){ ios::sync_with_stdio(0); cin >> n; for (int i = 1; i < n; ++ i ) cin >> x >> y, add(x, y), add(y, x); dfs(1, 0, 1); dfs(sec, 0, 1); if((fir + 1) % 3 == 2) cout << "Second"; else cout << "First"; return 0; }