P3174 [HAOI2009]毛毛虫 题解

CSDN同步

原题链接

简要题意:

给定一棵树,求最长的 “挂链” 长度。

挂链定义为:一条链上所有节点与其相连的节点构成的生成树。(非严谨定义)(原题中是 “毛毛虫”,本人以为挂链更形象)

这题有多种做法,这里给出思路,以及其中一种做法的代码。

算法一

注意到,其实我们只需要选出 “最长链”,然后在最长链的两侧挂链即可。

即,先求出 树的直径 的两个端点,然后遍历一遍直径上的端点,把它们的直接连边都加入生成树中。

最后统计答案即可。

时间复杂度:(O(n)).

期望得分:$100pts$.

算法二

考虑树形 ( ext{dp}),用 (f_i) 表示以 (i) 为根的最大挂链长度,(sub_i) 记录 (i) 的儿子个数,则:

(f_u = max(f_v , f_v + sub_u - 1) (v in operatorname{son} (u)))

很显然,要么直接继承儿子节点的答案,要么把两边一拼。

时间复杂度:(O(n)).

期望得分:$100pts$.

算法三

给出一个最巧妙的算法。

假设 (i) 号点的度是 (a_i),则一条长度为 (s) 的挂链的答案应该是:

(igg ( sum_{i in operatorname{list}} a_i igg ) -(s-1) + 1)

(i in operatorname{list}) 表示 (i) 属于当前链,(s-1) 即把重复计算的边去掉得到边数,然后 (+1) 得到点数。化简即:

$$ = igg ( sum_{i in operatorname } a_i igg ) - s + 2$$

你发现这个东西有点难看,于是换了一下:

$$ =sum_{i in operatorname } (a_i - 1) + 2$$

显然,把 (s) 减到每个节点里面 ,每个点分 $1$ 个。

那么我们可以按照如下步骤求解:

  1. 建图统计度,并将度 (-1).

  2. 求出直径两端。

  3. 统计直径上所有节点的度,然后 (+2) 即为答案。

时间复杂度:(O(n)).

实际得分:$100pts$.

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=3e5+1;

inline int read(){char ch=getchar();int f=1; while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();}
	   int x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}

int n,m,du[N],dis[N];
int num,mx;
vector<int> G[N];

inline void dfs(int dep,int fa,int dis) {
//fa 是 dep 的父亲 , dep 是正在搜索的节点,dis 是它与开始搜索节点的距离,dis 统计度和
	if(dis>mx) mx=dis,num=dep; //度和打擂
	for(int i=0;i<G[dep].size();i++)
		if(G[dep][i]!=fa) dfs(G[dep][i],dep,dis+du[dep]); //往下搜索
}

int main(){
	n=read(),m=read();
	memset(du,-1,sizeof(du)); //初始化为 -1, 即减掉 1
	while(m--) {
		int x=read(),y=read();
		G[x].push_back(y);
		G[y].push_back(x);
		du[x]++; du[y]++; //统计度
	} dfs(1,0,du[1]); mx=0;
	dfs(num,0,du[num]); //两次 dfs 寻找直径
	printf("%d
",mx+2); // +2 就是答案
	return 0;
}

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/bifanwen/p/12642080.html