CSES-1132 Tree Distances I（树的直径）
题目传送门
https://vjudge.net/problem/CSES-1132
解题思路
本题是贪心题……
首先求出树的直径，对于每一个点，它的最大距离应该就是到直径两端点的距离的最大值……
代码
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> g[200001];
int f[200001],mx,d1,d2;
int ans[200001];
void dfs(int x,int fa)
{
for(auto y:g[x])
{
if(y!=fa)
{
f[y]=f[x]+1;
if(f[y]>f[mx])mx=y;
dfs(y,x);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
int u,v;
for(int i=1;i<n;i++)
{
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,1);
f[mx]=0;
d1=mx;
dfs(mx,mx);
d2=mx;
f[d1]=0;
dfs(d1,d1);
for(int i=1;i<=n;i++)
{
ans[i]=f[i];
}
f[d2]=0;
dfs(d2,d2);
for(int i=1;i<=n;i++)
{
ans[i]=max(ans[i],f[i]);
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
}