题解：P12747 [POI 2016 R3] 庆典巡游 Parade

leozhao123 · 2025-06-23 19:05:41 · 题解

传送门 | AC 记录

题意：给定树，对于一条起点与终点不同的简单路径 P，称它的「权值」为满足 u\in V_P 且 v\notin V_P 的边 (u,v) 的数量。求所有 P 的权值的最大值。

先不考虑起点与终点是否相同。记 f_u 为以节点 u 为起点、u 的子树中的节点（包括 u）为终点的所有路径的权值的最大值。

• 当 u 的子树是菊花图时，即 u 的所有儿子都是叶子，此时选择任意一个儿子作为终点的路径的权值都为 |son_u|-1，而选择 u 本身作为终点则为 |son_u| 更优，因此 f_u=|son_u|。
• 当 u 的子树不是菊花图时，易得： f_u=\max_{v\in son_u}\set{f_v}+|son_u|-1

统计答案时用相同方法下传向上部分的 f 值即可。

最后考虑起点与终点相同的情况。按照转移，当且仅当给定的树是菊花图时，求出的起点与终点同为树的中心。由于最少取 2 个点，所以答案最大为 n-2，在输出时要将结果与 n-2 取较小值。

时间复杂度 \mathcal{O}(n)。

// -std=c++14 -O2
#include<vector>
#include<iostream>
using namespace std;
using ll=long long;
const ll N=2e5+3;
ll n,f[N],d[N],ans;
// d[u]=v 表示节点 u 继承了 f[v] (v\in son_u)
vector<ll>G[N];
void dfs1(ll u,ll fa) {// 求 f 和 d 数组
    for(auto v:G[u]) {
        if(v==fa) continue;
        dfs1(v,u);
        if(f[u]<f[v]) f[u]=f[v],d[u]=v;
    }
    fa=(u==1?0:1);// 注意 fa 的意义发生了改变，表示 u 有 / 没有父节点
    if(G[u].size()-fa>0) {
        if(f[u]) f[u]+=G[u].size()-fa-1;// 非菊花图情况
        else f[u]=G[u].size()-fa,d[u]=0;// 菊花图情况
    }
}
void dfs2(ll u,ll fa,ll g) {// g 为下传的向上部分的 f 值
    ans=max(ans,max(g,(u==1?0LL:1LL))+f[u]);
    for(auto v:G[u]) {
        if(v==fa) continue;
        if(d[u]!=v)
             dfs2(v,u,max((ll)(g+G[u].size()-2),f[u]-1+(u==1?0:1)));
        else dfs2(v,u,max((ll)(g+G[u].size()-2),f[u]-f[v]+(u==1?0:1)));
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll u,v;
    cin>>n;
    for(ll i=1;i<=n-1;++i) {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0,0);
    cout<<min(ans,n-2);
    return 0;
}