资源限制 时间限制：100ms 内存限制：8.0MB 问题描述 树的直径 输入格式 输入的第一行包含一个整数n，表示树中的点数。接下来n-1行，每行3个正整数，表示连同的两点及边的权值。 输出格式 输出1行，包含一个整数，表示树的直径。 样例输入 7 1 2 1 1 3 1 2 4 1 3 5 1 4 7 1 4 6 1 样例输出 5 数据规模和约定 n<10^5
//树的直径,深搜找到最远点，再用最远点找到直径,不是森林 #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxn = 100005; int n; struct node{ //采用结构体来保存邻接表 int v; int w; //权值 int front; //存储前一条边的序号 }edge[maxn]; int cnt = 0; int head[maxn]; //采用链式向前星 bool vis[maxn]; void add() { int u,v,w; scanf("%d %d %d",&u,&v,&w); edge[cnt].v = v; edge[cnt].w = w; edge[cnt].front = head[u]; head[u] = cnt++; edge[cnt].v = u; edge[cnt].w = w; edge[cnt].front = head[v]; head[v] = cnt++; } int deepl = 0; int maxd; void dfs(int u,int step) { //这个应该要还原现场 if(step>deepl) { maxd = u; deepl = step; } for(int i = head[u];i!=-1;i=edge[i].front) { int v=edge[i].v; if(!vis[v]) { vis[v]=true; dfs(v,step+edge[i].w); vis[v] = false; } } return; } int main() { scanf("%d",&n); memset(head,-1,sizeof(head)); //这里一定要全部初始化，不然很有可能出现错误 memset(vis,false,sizeof(vis)); for(int i = 1;i<=n-1;i++) { add(); } maxd = 1; vis[1] = true; dfs(1,0); vis[1] = false; vis[maxd] = true; dfs(maxd,0); printf("%d",deepl); return 0; }