题解：P17320 [ICPC 2018 Nanjing R] Cherry and Chocolate

lailai0916 · 2026-08-31 05:47:47 · 题解

题意简述

在树上依次选择粉色点、棕色点、粉色点。路径经过粉色点的节点会得分。Cherry 最大化得分，Chocolate 最小化得分，求最终得分。

解题思路

删除两个粉色点后，一个节点得分当且仅当它不在棕色点所在的连通块中。因此，若这个连通块大小为 s，得分就是 n-s。

固定第一个粉色点 u。删除 u 后，Chocolate 选择某个连通块 T，并在其中选择棕色点 v。设 |T|=S。

若 S=1，棕色点所在连通块最终仍只有一个节点。以下只需讨论 S\ge2 的情况。

以 v 为根观察 T。Cherry 的第二个粉色点一定可以选为 v 的某个邻点；删除这个邻点后，其所在分支全部与 v 分离。选得更深只会截去这个分支的一部分，不会更优。因此 Cherry 会截去 v 的最大分支。

记删除 v 后最大连通块的大小为 b_v。此时棕色点最终所在连通块大小为 S-b_v。Chocolate 需要最大化这个值，也就是最小化 b_v。满足这一条件的点恰好是 T 的重心。

于是，对删除一条边后得到的每个连通块，只需知道其大小及重心处的最大分支大小。

将每条无向边拆成两条有向边。对有向边 e=(u,v)，记 T_e 为删除该边后包含 v 的连通块，大小为 s_e。在 v 的所有出边中排除 (v,u)，剩余出边对应 v 在 T_e 中的各个向前分支。

令 \operatorname{next}(e) 为这些出边中对应连通块最大的一个。若：

则 T_e 的重心必定位于这个唯一超过一半的分支中，可以沿 \operatorname{next}(e) 继续寻找。每次转移都会进入严格更小的连通块。所有转移构成一条不回头的有向链。

预处理每个节点最大、次大的出边，便能在排除反向边后求出 \operatorname{next}(e)。再对这个转移建倍增表。对起始边 e，设 S=s_e。从高位到低位跳过大小仍大于 S/2 的连通块，最终停在边 f。

停止时，所有向前分支大小均不超过 S/2。若 f\ne e，最后一次转移保证 s_f>S/2，故反向分支 S-s_f<S/2。若 f=e，反向分支为空。因此 f 的终点是 T_e 的一个重心。

该重心朝起始边方向的分支大小为 S-s_f，其余分支中的最大值为 s_{\operatorname{next}(f)}。故重心处的最大分支大小为：

若 \operatorname{next}(f) 不存在，将后一项视为 0。Chocolate 在 T_e 中能够保留的连通块大小为：

第一个粉色点为 u 时，Chocolate 会在各个相邻连通块中最大化 h_e。Cherry 再选择使这个最大值最小的 u。因此答案为：

倍增预处理和逐边查询的时间复杂度均为 O(n\log n)，空间复杂度为 O(n\log n)。

参考代码

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

const int N=100005;
const int M=200005;
const int K=18;
vector<int> g[N];
int to[M],siz[M],val[M];
int fa[N],ped[N],sub[N],fst[N],sec[N];
int nxt[K][M];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int m=2*n-2;
    for(int i=0;i<m;i+=2)
    {
        int u,v;
        cin>>u>>v;
        to[i]=v;
        to[i^1]=u;
        g[u].push_back(i);
        g[v].push_back(i^1);
    }
    vector<int> ord(1,1);
    for(int i=0;i<n;i++)
    {
        int u=ord[i];
        for(int e:g[u])
        {
            int v=to[e];
            if(v==fa[u])continue;
            fa[v]=u;
            ped[v]=e;
            ord.push_back(v);
        }
    }
    for(int i=1;i<=n;i++)sub[i]=1;
    for(int i=n-1;i>0;i--)
    {
        int u=ord[i];
        sub[fa[u]]+=sub[u];
        siz[ped[u]]=sub[u];
        siz[ped[u]^1]=n-sub[u];
    }
    for(int i=1;i<=n;i++)
    {
        fst[i]=sec[i]=-1;
        for(int e:g[i])
        {
            if(fst[i]==-1||siz[e]>siz[fst[i]])
            {
                sec[i]=fst[i];
                fst[i]=e;
            }
            else if(sec[i]==-1||siz[e]>siz[sec[i]])sec[i]=e;
        }
    }
    for(int i=0;i<m;i++)
    {
        int v=to[i];
        nxt[0][i]=fst[v]!=(i^1)?fst[v]:sec[v];
    }
    for(int i=1;i<K;i++)
    {
        for(int j=0;j<m;j++)
        {
            int ne=nxt[i-1][j];
            nxt[i][j]=ne==-1?-1:nxt[i-1][ne];
        }
    }
    for(int i=0;i<m;i++)
    {
        int f=i;
        for(int k=K-1;k>=0;k--)
        {
            int ne=nxt[k][f];
            if(ne!=-1&&siz[ne]*2>siz[i])f=ne;
        }
        int mx=siz[i]-siz[f];
        if(nxt[0][f]!=-1)mx=max(mx,siz[nxt[0][f]]);
        val[i]=siz[i]-mx;
    }
    int ans=n;
    for(int i=1;i<=n;i++)
    {
        int mx=0;
        for(int e:g[i])mx=max(mx,val[e]);
        ans=min(ans,mx);
    }
    cout<<n-ans<<'\n';
    return 0;
}