P7238 迷失森林 题解

发表于 分类于

本文迁移自洛谷原文。

这里是验题人的思路（不同于官方题解）

将所有的树都缩成一个点。
对于第 $i$ 棵树，如果与第 $j$棵树有边，那么 $dist_{i,j}$ 为第 $i$ 棵树的 $i$ 号点到第$j$ 棵树的 $j$ 号点的距离。

叶子节点要特判。

尤其要特判当1号节点为叶子（只有一条出边）时的情况。

最后对新图求直径即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int maxn=100004;
char buffer[maxn],*S,*T;
inline char Get_Char(){
    if(S==T){
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}

inline int read(){
    char c;
    ri re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)return -re;
    return re;
}

inline void read(int&x){
    char c;
    ri re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
const int mxn=1e6+6;
vector<int>f[mxn];
vector<pair<int,int> >g[mxn];
int n,root;
int u[mxn],v[mxn];
int pa[mxn];
int dep[mxn];
int max_deep;
int mxdp[mxn];
inline void dfs1(int x,int par=-1,int deep=1){
	mxdp[x]=1;
	dep[x]=deep;pa[x]=par;
	max_deep=max(max_deep,deep);
	for(ri i=0;i<f[x].size();++i){
		ri y=f[x][i];
		if(y!=par)dfs1(y,x,deep+1),mxdp[x]=max(mxdp[x],mxdp[y]+1);
	}
}
ll dist[mxn];
inline void dfs2(int x,int par=-1,ll dst=0){
	dist[x]=dst;
	for(ri i=0;i<g[x].size();++i){
		ri y=g[x][i].first;ll w=g[x][i].second;
		if(y!=par)dfs2(y,x,dst+w);
	}
}
inline void solve(){
	read(n);
	for(ri i=1;i<n;++i){
		read(u[i]),read(v[i]);
		f[u[i]].push_back(v[i]);
		f[v[i]].push_back(u[i]);
	}
	root=1;
	dfs1(root);//对原树进行处理
	for(ri i=1;i<n;++i){   //将树缩成点
		if((u[i]==1 or v[i]==1) and f[1].size()==1){
			int t;
			if(u[i]==1)t=v[i];
			else t=u[i];
			g[u[i]].push_back(mp(v[i],max_deep+dep[t]-1));
			g[v[i]].push_back(mp(u[i],max_deep+dep[t]-1));
		}else if(f[u[i]].size()==1 or f[v[i]].size()==1){
			g[u[i]].push_back(mp(v[i],max_deep));
			g[v[i]].push_back(mp(u[i],max_deep));
		}else if(u[i]==pa[v[i]]){
			g[u[i]].push_back(mp(v[i],dep[v[i]]));
			g[v[i]].push_back(mp(u[i],dep[v[i]]));
		}else{
			g[u[i]].push_back(mp(v[i],dep[u[i]]));
			g[v[i]].push_back(mp(u[i],dep[u[i]]));
		}
	}
	memset(dist,63,sizeof(dist)); //求直径
	dfs2(root);
	ri place;
	place=1;
	for(ri i=1;i<=n;++i)if(dist[i]>dist[place])place=i;
	memset(dist,63,sizeof(dist));
	dfs2(place);
	ll Max=0;
	for(ri i=1;i<=n;++i)Max=max(Max,dist[i]);
	printf("%lld\n",Max+1);
}
int main(){
	ios_base::sync_with_stdio(false);
	int T=1;//cin>>T;
	for(;T--;)solve();
	return 0;
}