树的直径

树的直径

概念

给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。

题目描述

给定一个有个节点的树，树以个点条边的无向图形式给出， 求树的直径。 输入格式 输入的第1行为包含了一个正整数，为这棵二叉树的结点数。 接下来N行，每行有个正整数，表示有一条从到的无向边。 输出格式 输出包括1个正整数，为这棵二叉树的直径。 样例 样例输入 10 1 2 1 3 2 4 4 5 4 6 1 7 5 8 7 9 7 10 样例输出 6

分析

跑2个dfs，第一个求以根为起点的最短距离，第二个求一最长距离终点为起点的最长距离，ans为第二个

#include <bits/stdc++.h> using namespace std; int n; int x, y; vector<int> g[100005]; int dp[1000005]; int ans; int jl; void dfs(int x, int fa) { if (ans < dp[x]) { ans = dp[x]; jl = x; } for (int i = 0; i < g[x].size(); i++) { int v = g[x][i]; if (v == fa) { continue; } dp[v] = dp[x] + 1; dfs(v, x); } } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d %d", &x, &y); g[x].push_back(y); g[y].push_back(x); } ans = 0; dp[1] = 0; dfs(1, 0); ans = 0; dp[jl] = 0; dfs(jl, 0); printf("%d", ans); }