旅游规划
旅游规划
$W$ 市的交通规划出现了重大问题，市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。
但由于人员不足，$W$ 市市长决定只在最需要安排人员的路口安排人员。
具体来说，$W$ 市的交通网络十分简单，由 $n$ 个交叉路口和 $n?1$ 条街道构成，交叉路口路口编号依次为 $0,1,…,n?1$ 。
任意一条街道连接两个交叉路口，且任意两个交叉路口间都存在一条路径互相连接。
经过长期调查，结果显示，如果一个交叉路口位于 $W$ 市交通网最长路径上，那么这个路口必定拥挤不堪。
所谓最长路径，定义为某条路径 $p= \left( {v_{1},v_{2},…,v_{k}} \right)$，路径经过的路口各不相同，且城市中不存在长度大于 $k$ 的路径（因此最长路径可能不唯一）。
因此 $W$ 市市长想知道哪些路口位于城市交通网的最长路径上。
输入格式
第一行包含一个整数 $n$。
之后 $n?1$ 行每行两个整数 $u,v$，表示编号为 $u$ 和 $v$ 的路口间存在着一条街道。
输出格式
输出包括若干行，每行包括一个整数——某个位于最长路径上的路口编号。
为了确保解唯一，请将所有最长路径上的路口编号按编号顺序由小到大依次输出。
数据范围
$1 \leq n \leq 2 \times {10}^{5}$
输入样例：
10 0 1 0 2 0 4 0 6 0 7 1 3 2 5 4 8 6 9
输出样例：
0 1 2 3 4 5 6 8 9
解题思路
题意就是求树的直径上的所有点，其中可能存在多条树的直径。
这里用树形dp来求树的直径。
对于一颗树，当我们选定一个点为根后，那么对于任何一条路径，都存在一个唯一的最高点。即不管是哪条路径，其最高点是唯一的。如图：
直径是所有路径里面的最大值。将所有路径按照最高点进行分类，划分集合，则最高点为$1$的是一类，最高点为$2$的是一类，......，以此类推，一共可以分成$n$组，树的直径就是某一组中的路径的最大值。
记每个以$i$为最高点，且以$i$为端点的所有路径的最大值为$d_{1}\left[ i \right]$，次大值为$d_{2}\left[ i \right]$。
对于根节点，先求出所有子节点的最大路径（即以子节点端点的最长的路径长度，同时子节点也是这条路径的最高点）$d_{1}\left[ i \right]$。然后从这些$d_{1}\left[ i \right]$中，找到最大值和次大值，从而得到以根节点为最高点的，且以根节点为端点的所有路径的最大值$d_{1}\left[ root \right]$和次大值$d_{2}\left[ root \right]$。
接下来我们从根节点出发，选择两个以子节点为端点的路径与根节点连成一条更长的路径，此时根节点仍为路径的最高点，但路径不是以根节点为端点了。要使得路径长度最大，就是$d_{1}\left[ root \right] + d_{2}\left[ root \right]$。同时这条最长路径，对应以根节点为最高点的那个集合的最大值。
因此要求树的直径，就是求以每一个结点为根节点的$d_{1}\left[ root \right] + d_{2}\left[ root \right]$，树的直径就是这些值中的最大值。
求最大路径的题可以看这篇博文：大臣的旅费：https://www.cnblogs.com/onlyblues/p/15940402.html
但这题并不是求树的直径，而是树的直径上的所有点。方法是遍历每一个点，看一下这个点是否在树的直径上。即选择两个与该结点相邻的结点（叶子结点除外），将以这两个结点为端点的路径与该结点相连，与上面的做法相同，判断这条连接的路径是否为树的直径就可以了。
对于树中任何一个结点，都有一个向上的结点（这个结点的父节点）和向下的若干个结点（子节点。叶子结点除外）。对于向下的子节点，前面我们已经求得最大路径长度$d_{1}\left[ root \right]$和次大路径长度$d_{2}\left[ root \right]$。对于向上的父结点，这里记向上的最大路径长度为$up \left[ root \right]$，表示以根节点为端点（不是最高点）的一条向上的路径，这条路径长度的取值又取决于其父节点的$up \left[ fa \right]$，并且要取尽可能大的值。我们就是要找到$d_{1}\left[ root \right]$、$d_{2}\left[ root \right]$、$up \left[ root \right]$这三个的最大值和次大值，两者相加，如果长度等于树的直径，那么这个点就在树的直径上，否则不在。
从根节点往上走，走的到父节点，再从父节点走的话又可以走多远。这个最远的值加上$1$就是$up \left[ root \right]$。从根节点的父节点$fa$走有两种值：
- 从$fa$往上继续走，$up \left[ fa \right]$。
- 从$fa$往下走：
- 如果根节点$root$在$d_{1}\left[ fa \right]$这条路径上，那么不能用这条路径。由于要取尽可能大的值，因此这种情况要选择$d_{2}\left[ fa \right]$。
- 如果根节点$root$不在$d_{1}\left[ fa \right]$这条路径上，那么就取$d_{1}\left[ fa \right]$。
最后$up \left[ fa\right]$就是这两种情况的最大值。
为了判断根节点$root$是否在$d_{1}\left[ fa \right]$这条路径上，这里还需要开一个数组来记录每个结点的最长路径$d_{1}\left[ root \right]$所对应的那个子节点。
求$d_{1}\left[ root \right]$、$d_{2}\left[ root \right]$是一个自下而上的过程，而求$up \left[ root \right]$则是一个自上而下的过程。
AC代码如下：
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int N = 2e5 + 10, M = N << 1; 7 8 int head[N], e[M], ne[M], idx; 9 int d1[N], d2[N], son[N], up[N]; 10 int maxd; 11 12 void add(int v, int w) { 13 e[idx] = w, ne[idx] = head[v], head[v] = idx++; 14 } 15 16 void dfs_d(int src, int pre) { 17 for (int i = head[src]; i != -1; i = ne[i]) { 18 if (e[i] != pre) { 19 dfs_d(e[i], src); // 求子节点的最大路径长度 20 21 // 更新根节点的最大路径长度和次大路径长度 22 int d = d1[e[i]] + 1; 23 if (d > d1[src]) { 24 d2[src] = d1[src]; 25 d1[src] = d; 26 son[src] = e[i]; 27 } 28 else if (d > d2[src]) { 29 d2[src] = d; 30 } 31 } 32 } 33 34 maxd = max(maxd, d1[src] + d2[src]); // 树的直径就是每个结点的d1+d2，取最大值 35 } 36 37 void dfs_up(int src, int pre) { 38 for (int i = head[src]; i != -1; i = ne[i]) { 39 if (e[i] != pre) { 40 // 自下而上的过程，当枚举都某个结点时，这个结点的up值已经确定，则其子节点的up值也就确定了 41 if (son[src] == e[i]) up[e[i]] = max(up[src], d2[src]) + 1; // 如果子节点在src的d1这条路径上，那么不可以取d1[src] 42 else up[e[i]] = max(up[src], d1[src]) + 1; // 如果子节点不在src的d1这条路径上，可以取d1[src] 43 dfs_up(e[i], src); 44 } 45 } 46 } 47 48 int main() { 49 memset(head, -1, sizeof(head)); 50 51 int n; 52 scanf("%d", &n); 53 for (int i = 0; i < n - 1; i++) { 54 int v, w; 55 scanf("%d %d", &v, &w); 56 add(v, w), add(w, v); 57 } 58 59 dfs_d(0, -1); 60 dfs_up(0, -1); 61 62 for (int i = 0; i < n; i++) { 63 int d[3] = {d1[i], d2[i], up[i]}; 64 sort(d, d + 3); 65 if (d[1] + d[2] == maxd) printf("%d\n", i); // 取每个结点的d1，d2，up中的最大的两个连成一条路径，再判断是不是树的直径长度 66 } 67 68 return 0; 69 }
参考资料
AcWing 1078. 旅游规划（蓝桥杯C++ AB组辅导课）：https://www.acwing.com/video/792/