1073. 树的中心 （树形dp）

题目 题意: 给定n个点的树，请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。 思路: 树形dp。一遍dfs求出每个点到其他节点的最远距离，之后枚举一遍即可。可以将一个节点分成向下走和向上走，向下走好说，dfs呼呼走就行。如果是向上走呢?我们可以维护次长路和最长路对应哪个儿子son，对于当前点cur 的儿子j，如果他是最长路对应的儿子son，up[j] = max(up[cur],d2[cur]) + w[i];否则，up[j] = max(up[cur],d1[cur]) + w[i].因为该点向上走肯定经过父节点，又要选最长的路，分情况讨论即可。 时间复杂度: O(n) 代码:

#include
using namespace std;
int n,m,k,T;
const int N = 1e5+10;
#define mem(a,x) memset(a,x,sizeof(a))
int h[N],e[N>y>>z;
		add(x,y,z),add(y,x,z);
	}
	dfs(1,0);
	dfs2(1,0);
	int mx = 1e9;
	for(int i=1;i