大致步骤

换根dp 大致步骤

方法一：（up数组）
(1) g[i] 以i为根的子树（不是整棵树），由孩子节点推过来
(2) up[i] i节点往上走的最大属性
(3) f[i] 整棵树（不是子树） 记录一些值

方法二：加减法

(1) g[i] 以i为根的子树（不是整棵树），由孩子节点推过来

(2) f[i] 整棵树（不是子树） 记录一些值（通过加减法，用g数组计算f数组）

这就是一些通用套路了，下面会详细讲解如何使用

深度最大（方法一）

给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，该树深度最大。深度定义为叶子节点到根的简单路径上边的数量最大值。1≤n≤1e6，1≤u,v≤n

输入格式

第一行有一个整数，表示树的结点个数 n。

接下来 (n−1) 行，每行两个整数 u,v，表示存在一条连接 u,v 的边。

输出格式

输出一行一个整数表示你选择的结点编号。如果有多个结点符合要求，输出节点编号最小值。

输入/输出例子1

输入：

2

1 2

输出：

1

样例解释

无

例题1（换根1：up数组）

g(i, 0/1)：以i为根的子树，0:次大深度，1:最大深度
通常记录最大的情况下，要记录次大值

第一步. O(n)

如何更新次大值，最大值？
假设v是i的子树，子推父

1) if (g[v][1]+w >= g[i][1])
g[i][0]=f[i][1], g[i][1]=g[v][1]+w //注意顺序，先更新最大值，再更新次大值
son[i]=v //后面解释

2) if (g[v][1]+w<f[i][1])
g[i][0]=max(g[i][0], g[v][1]+w)

3) 最重要的数组:
son[i] 以i为根的子树，是哪个儿子给i最大贡献

第二步. O(n)

怎么更新up数组？
up[root]=0
父推子，假设i是u的孩子，i-u直接相连的边权值为w

分情况，u往上走，u往下走
1) up[i]=max(w+up[u], up[i])

u往下走的最远距离，是不是i往上能走到的？那不就是最远距离了吗，但是要注意u走过的路径不能和i重叠，不然i就变成往下走了，所以如果重叠，换次长路，这是肯定不会经过i
2) if (son[u]==i) up[i]=max(up[i], w+g[u][0])
else up[i]=max(up[i], w+g[u][1])

第三步

f[i]=max(g[i][1], up[i])
ans=max(ans, f[i])