自动搬运

查看原文

来自洛谷，原作者为

	leozhao123 不是这咕值要多久才能掉到 0 啊

搬运于2025-08-24 23:17:52，当前版本为作者最后更新于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;
}