hihoCoder week11 树中的最长路

题目链接: https://hihocoder.com/contest/hiho11/problem/1

求树中节点对 距离最远的长度

#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + ;
int n;
vector<int> G[N];
int d[N];
void dfs(int u, int fa)
{
for(int i=; i<G[u].size(); i++) {
int v = G[u][i];
if(v != fa) {
d[v] = d[u] + ;
dfs(v, u);
}
}
} int main()
{
freopen("in.txt", "r", stdin);
scanf("%d",&n);
for(int i=; i<n-; i++) {
int a,b; scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
d[] = ;
dfs(, );
int mx = ;
int index = -;
for(int i=; i<=n; i++) {
if(mx < d[i]) {
mx = d[i];
index = i;
}
}
//printf("%d\n", mx);
memset(d,,sizeof(d));
dfs(index, );
for(int i=; i<=n; i++) {
if(mx < d[i]) {
mx = d[i];
index = i;
}
}
cout << mx <<endl;
return ;
}
#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + ;
vector<int> G[N];
int n, ans; int dfs(int u,int fa)
{
int l1=-,l2=-;
for(int i=; i<G[u].size(); i++) {
int v = G[u][i];
if(v == fa) continue;
int l = dfs(v, u);
if(l > l1)
l2=l1 , l1=l;
else
l2 = max(l2, l); }
//cout << u <<" "<< l1 <<" "<< l2 <<endl;
ans = max(ans , l1 + l2 + );
// cout << u <<" 最长的路为" <<l1 <<endl;
return l1+;
} int main()
{
//freopen("in.txt", "r", stdin);
cin >> n;
for(int i=; i<n; i++) {
int a,b; scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
ans = ;
dfs(,);
cout << ans <<endl;
return ;
}
上一篇:Vue使用html2canvas将页面转化为图片下载到本地


下一篇:SQLAlchemy 快速入门、基础知识