知识点1:怎么判断一个图是树呢?
他的 点数 = 边数 + 1
知识点2:树,怎么求任意两点之间的最长距离呢?也就是树的直径
1.用随便一个点求一遍DFS,求出距离这个点最长的点(一般用D[i]来存)
2.用这个最长的点,再求一遍最长距离,就是整个树里面的最长距离。
tips:记得两次DFS,以及多组输入的题中,要刷新记录的值
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<stdlib.h>
using namespace std;
const int N = 100050;
bool vis[N];//dfs中是否遍历过
vector<pair<int,int> > vec[N];//存图
int n ;
long long int d[N];//从1 到 i 的最长距离
void dfs(int u,long long int wu){//dfs遍历,wu是指从确认的起始点遍历到目前的点的距离
int len = vec[u].size();
d[u] = max(d[u],wu);
for(int i = 0 ; i < len ; i ++){
int v = vec[u][i].first;
int w = vec[u][i].second;
if(!vis[v]){
vis[v] = true;
dfs(v,wu + w);
vis[v] = false;
}
}
}
int main(){
cin>>n;
int u,v,w;
for(int i = 1 ; i < n ; i ++){
cin>>u>>v>>w;
pair<int , int > p(v,w);
pair<int,int > pp(u,w);
vec[u].push_back(p);
vec[v].push_back(pp);
}
vis[1] = true;
dfs(1,0);
vis[1] = false;
long long int Max = 0,Maxindex;
for(int i = 1 ; i <= n ; i ++ ){
if(d[i]>Max){
Maxindex = i;
Max = d[i];
}
}
//cout<<Maxindex<<endl;
memset(d,0,sizeof(d));
//memset(vis,0,sizeof(vis));
vis[Maxindex] = true;
dfs(Maxindex,0);
vis[Maxindex] = false;
for(int i = 1 ; i <= n ; i ++ ){
//cout<<d[i]<<" ";
if(d[i]>Max){
Max = d[i];
}
}
cout<<(10 * Max + (Max) * (Max + 1) / 2)<<endl;
return 0;
}