AcWing 1078. 旅游规划
原题链接
中等
作者:
wjie
,
2020-07-05 21:32:17
,
所有人可见
,
阅读 584
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2e5 + 5;
vector<int> G[N];
int f[N][3], dis[N], maxDis;
void dfs1(int u, int father)
{
int one = 0, two = 0;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (v == father)
continue;
dfs1(v, u);
int tmp = f[v][0] + 1;
if (tmp >= one)
{
two = one;
one = tmp;
}
else
two = two > tmp ? two : tmp;
}
f[u][0] = one, f[u][1] = two;
}
void dfs2(int u, int father)
{
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (v == father)
continue;
//f[v][2]
if (f[v][0] + 1 == f[u][0])
f[v][2] = max(f[u][1], f[u][2]) + 1;
else
f[v][2] = max(f[u][0], f[u][2]) + 1;
dis[v] = max(f[v][1], f[v][2]) + f[v][0];
maxDis = maxDis > dis[v] ? maxDis : dis[v];
dfs2(v, u);
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
int root = 0;
dfs1(root, -1);
dfs2(root, -1);
dis[root] = f[root][0] + f[root][1];
for (int i = 0; i < n; ++i)
{
if (dis[i] == maxDis)
printf("%d\n", i);
}
return 0;
}