2021.08.09 P7238 迷失森林（树的直径）

2021.08.09 P7238 迷失森林（树的直径）

P7238 「DCOI」迷失森林 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.树的直径两种求法：两次dfs、树形dp

题意：

首先给出一棵以 11 为根，nn 个结点的树，定义为「单位树」。

现有 nn 个结构与「单位树」完全相同的树，要将 nn 个树再用 n-1n−1 条边连接起来。

为方便叙述，用符号 (a,b)(a,b) 表示结点 aa 所代表树中，编号为 bb 的结点。

连接方式如下：

将 nn 棵树按照「单位树」的结构摆放好。
对于每个 ii(1<i≤n)，连接结点 (i,1)和 (f_i,f_i)。其中 f_i 表示「单位树」中结点 i 的父亲。

求将 nn 棵树连接后，整棵包含 n^2n2 个结点的树中，树上两点简单路径所包含的 结点 个数的最大值。

分析及代码：

//节点最多的路径：树的直径。另一条是啥？

//遍历这棵树，寻找dep最深和第二深的两个节点之和-1

//好吧，我眼瞎，求个树的直径就行，而且要求lca为1

//暴力建边dfs求树的直径是O(n^2)，望天~

//只能树形dp

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=1e6+10;

ll n,ans,maxn,dep[N],f[N];

int cnt,head[N];

struct node{

	int to,next;

}a[N<<1];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void add(int u,int v){

	++cnt;

	a[cnt].to=v;

	a[cnt].next=head[u];

	head[u]=cnt;

}

void dfs(int x,int fa){

	dep[x]=dep[fa]+1;

	maxn=max(maxn,dep[x]);

	for(int i=head[x];i;i=a[i].next){

		int v=a[i].to;

		if(fa==v)continue;

		dfs(v,x);

	}

}

void dfsi(int x,int fa){

	f[x]=maxn;//f_i表示在(i,1)为根的子树中，以(i,1)为起点的最长的链

	ll max1=0,max2=0;

	for(int i=head[x];i;i=a[i].next){

		int v=a[i].to;

		if(v==fa)continue;

		dfsi(v,x);

		f[x]=max(f[x],f[v]+dep[x]);

		if(max1<f[v])max2=max1,max1=f[v];

		else if(max2<f[v])max2=f[v];

	}

	ans=max(ans,max1+max2+1);

}

int main(){

	n=read();

	for(int i=1;i<n;i++){

		int u,v;

		u=read();v=read();

		add(u,v);

		add(v,u);

	}

	dfs(1,1);dfsi(1,1);

	ans=max(ans,f[1]+maxn-1);

	cout<<ans;

	return 0;

}

2021.08.09 P7238 迷失森林（树的直径）的相关教程结束。