题解：P15166 [SWERC 2022] Parmigiana With Seafood

· · 题解

P15166 [SWERC 2022] Parmigiana With Seafood

link

呜呜呜好神奇的题。

考虑二分答案，我们把 \ge mid 的点标记为 1，<mid 的点标记为 0，先手只需要选择任意一个 1 点即可获胜，而后手选择完所有 1 点获胜。

我们来刻画一下先手/后手获胜的条件。如果有一个 1 点是叶子节点那么先手直接获胜了。否则后手在进行一次操作后不能使任何一个 1 点成为叶子节点，那么我们考虑任意一些 1 点集合所形成的虚树，这个虚树中如果有叶子结点为 1 点，我们再随便加入一条一个端点为这个 1 点的边。我们发现拆掉这个虚树的任意一个叶子节点，都会导致一个 1 点成为叶子节点。如果 siz_{tree}\not\equiv n \pmod 2，那么此时后手操作，之后先手一定可以选一个 1 点，后手就输了。于是我们只需要判断是否存在这样的虚树满足 siz_{tree}\not\equiv n \pmod 2 即可。

  2. 存在 1 点 (u, v)，\operatorname{dis}(u, v)\bmod 2=1，那么 (u, v) 形成的虚树满足条件
  3. 存在 1 点 (u, v, w)，它们的中心为 x，u,v,w 到 x 的距离都是偶数，那么 (u, v, w) 形成的虚树满足条件。

可以证明上面三条囊括了所有情况。此时我们不需要再二分答案，直接维上面几种情况 \min(u, v) 或 \min(u, v, w) 的最大值即可。另外我们发现第二种情况 (u, v) 中有 u=n 或 v=n，第三种情况中有 u,v,w,x 中一个为 n，否则可以证明一定不优。那么容易 dfs 做到 O(n)。


#include<bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
#define per(i, j, k) for(int i=(j); i>=(k); --i)
const int N=1e5+3;
int n, d[N], dep[N], ans, f[N];
vector<int> G[N];

void dfs(int u, int pre){
  vector<int> d;
  if(!dep[u]) f[u]=u;
  else ans=max(ans, u);
  for(auto v:G[u]) if(v!=pre){
    dep[v]=!dep[u];
    dfs(v, u);
    f[u]=max(f[u], f[v]);
    d.emplace_back(f[v]);
  }
  sort(d.begin(), d.end(), greater<int>());
  if(!pre && d.size()>=3) ans=max(ans, d[2]);
  else if(pre && d.size()>=2 && !dep[u]) ans=max(ans, d[1]);
}

signed main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>n;
  rep(i, 2, n){
    int u, v;
    cin>>u>>v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  rep(i, 1, n) if(G[i].size()==1) ans=max(ans, i);
  dfs(n, 0);
  if(n%2==0) ans=n;
  cout<<ans;
}