Diameter_of_tree

树的直径

定义

树的直径，又称树的最长链，定义为一棵树上最远的两个节点的路径，即树上一条不重复经过某一条边的最长的路径。树的直径也可以代指这条路径的长度。

求解方式

求树的直径有两种比较常用的方法：树形DP和搜索，时间复杂度均为$O(n)$。

树形dp

关于树形dp更具体的介绍可以见我的这篇博客：dynamic-programming-advance

树形dp类的问题大多都需要同时借助于dfs来同步更新数据，所以这类主要有两个难点，一个是dfs的书写顺序（比如先进dfs还是先更新数据之类的顺序问题），一个是状态转移方程的求解。

而且由于dp类问题本身的特点，树形dp的做法无法获得整个树的直径上的各个结点，所以后面马上介绍的两次搜索的方法才是树的直径类问题的主流。

设$dis_x$表示从$x$走向以其为根的子树，能够到达的最远距离。再设$x$的$k$个子节点分别为$s_1,s_2,...,s_k$。显然可以得出关于$d$数组的转移方程：(其中$dist_{i,j}$表示$i,j$之间的距离)

for (int i = 1; i <= k; i++) {
    int next = s[i];
    dis[x] = max(dis[step], d[next] + dist(x, next));
}

设$l_x$表示经过$x$的最长链的长度，$dr$表示该树的直径，若该树有$n$个节点，则有：

for (int i = 1; i <= n; i++)
    dr = max(ans, l[i]);

那么如何推出$l$数组呢？对于$x$的任意两个子节点$s_u,s_v$，经过这三个节点的最长链显然为$d_{s_u}+dist_{s_u,x}+dist_{x,s_v}+d_{s_v}$。于是有以下的状态转移方程：

for (int i = 1; i <= k; i++) {
    for (int j = 1; j < i; j++) {
        l[x] = max(l[x], dis[s[i]] + dist(s[i], x) + dist(x, s[j]) + dis[s[j]]);
    }
}

因为$dr$就是所有$l_x$中的最大值，所以可以不必再多定义一个$l$数组，直接定义一个整形变量$ans$存储答案，每次直接更新就可以了。

这个状态转移方程还可以进一步优化。实际上，在运行时，对于任意两个点$u,v(v<u)$（这里假设循环时按编号从小到大的顺序遍历，即先遍历$v$，再遍历$u$），在循环到$u$时，根据$d_x$的转移方程，此时$d_x$内已经存储了编号小于$i$的所有$x$的子节点$v$的最大的$d_{s_v}+dist_{s_v,x}$。换句话说，就是实现了下面这个步骤：

for (int j = 1; j < i; j++){
    int next=s[j];
    dis[step] = max(dis[step], dis[next] + dist(step, next));    
}

因此，我们可以省去这一步，直接先用$d_x$来代替$max(d_{s_v}+dist(s_v,x))$来更新$l _x$，省去了一层循环，实现优化。注意，在这里一定要先更新$l_x$，再更新$d_x$。

树形DP求树的直径代码：

vector<int> v[M];
void dfs(int step, int fa) {
    for (int k = 0; k < ve[step].size(); k++) {
        int next = ve[step][k];
        if (next == fa)
            continue;
        dfs(next, step);
        ans = max(ans, dis[step] + dis[next] + dist(step, next));
        // 先更新l[x]
        dis[step] = max(dis[step], dis[next] + dist(step, next));
        // 再更新dis[x]
    }
}

两次dfs

通过两次搜索可以求出树的直径，同时还能求出具体路径。这里的搜索用DFS和BFS均可,笔者更喜欢用DFS，因为比较顺手。

两次dfs的算法思想是这样的，先从图上任意一点，搜索整棵树，找到距离该点最远的点，再用距离该点最远的点搜索一次，即可得到树的直径。

这个思路比较好懂，而且也比较容易证明，在此放个洛谷里的简单证明：SCAU_Lnn 的博客 ，这篇题解也是我下方模板题的思路来源。

要想实现这个思路，首先要使用树上dfs的经典模板：

邻接矩阵：

vector<int> v[M];
void dfs(int step, int fa) {
    for (int k = 0; k < v[step].size(); k++) {
        int next = v[step][k];
        if (next == fa)
            continue;
        dfs(next, step);
    }
    return;
}

邻接表：

void dfs(int step, int fa) {
    int k = g.head[step];
    while (k != -1) {
        int next = g.e[k].to;
        if (fa == next) {
            k = g.e[k].link;
            continue;
        }
        dfs(next, step);
        k = g.e[k].link;
    }
    return;
}

对于下面模板题而言，由于vector的扩展开发，使用邻接表和邻接矩阵都可以解决下面这题。所以从编码难度出发，我选择了较简单的邻接矩阵来讲解树的直径的相关题目。

由于两次dfs取得的是直径的两个端点，而许多题目需要用到的其实是直径上的各个点，所以我们需要在找两个端点时将路径保留下来。要想将路径保留下来，一个很好的方法是利用树的独特性质：对于除根节点以外的各个结点，每个结点有且只有一个父节点。所以我们第二次遍历时正是将其中一个端点作为根结点进行遍历的，只需要在这次dfs的过程中保留父节点的路径即可，具体其实只需要一行代码：

root[next] = step;

除此之外，在树的直径类的题目（其实也可以叫无根树类题目）中，对于某个指定了根的树，树的各个结点的深度，子树数量也都可以在dfs过程中顺便记录下来，在此提供完整的dfs代码。

void search(int step, int fa) {
    if (deep > maxi) {
        maxi = deep;
        t1 = step;
    }
    for (int k = 0; k < ve[step].size(); k++) {
        int next = ve[step][k];
        if (next == fa)
            continue;
        root[next] = step;
        search(next, step);
    }
}

然后就是两次调用dfs的书写了，这里我是用t1,t2对两个结点进行了记录，并用上面提到的以子找父的方法找到了这个半径的中点。

search(u, -1);
t2 = t1;
search(t1, -1);
int mid = t1;
for (int i = 1; i <= (maxi + 1) / 2; i++) {
    mid = root[mid];
}

这样树的直径相关的元素就求解完了。

模板题

【XR-3】核心城市

【XR-3】核心城市

题目描述

X 国有 $n$ 座城市，$n - 1$ 条长度为 $1$ 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。

X 国国王决定将 $k$ 座城市钦定为 X 国的核心城市，这 $k$ 座城市需满足以下两个条件：

1. 这 $k$ 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。
2. 定义某个非核心城市与这 $k$ 座核心城市的距离为，这座城市与 $k$ 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

输入格式

第一行 $2$ 个正整数 $n,k$。

接下来 $n - 1$ 行，每行 $2$ 个正整数 $u,v$，表示第 $u$ 座城市与第 $v$ 座城市之间有一条长度为 $1$ 的道路。

数据范围：

• $1 \le k < n \le 10 ^ 5$。
• $1 \le u,v \le n, u \ne v$，保证城市与道路形成一棵树。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

6 3
1 2
2 3
2 4
1 5
5 6

样例输出 #1

1

提示

【样例说明】

钦定 $1,2,5$ 这 $3$ 座城市为核心城市，这样 $3,4,6$ 另外 $3$ 座非核心城市与核心城市的距离均为 $1$，因此答案为 $1$。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define mod 1000000007
#define eps 1e-5
#define ll long long
#define db double
#define pii pair<int, int>
#define time_limit (double)clock() / CLOCKS_PER_SEC <= 0.95
vector<int> ve[M];
int dis[M];
int n, k, maxi;
int t1, t2;
int dp[M], ans[M];
int root[M];
void search(int step, int fa, int deep) {
    dis[step] = deep;
    if (deep > maxi) {
        maxi = deep;
        t1 = step;
    }
    for (int k = 0; k < ve[step].size(); k++) {
        int next = ve[step][k];
        if (next == fa)
            continue;
        root[next] = step;
        search(next, step, deep + 1);
    }
}
void dfs(int step, int fa, int deep) {
    dis[step] = deep;
    dp[step] = dis[step];
    for (int k = 0; k < ve[step].size(); k++) {
        int next = ve[step][k];
        if (next == fa)
            continue;
        dfs(next, step, deep + 1);
        dp[step] = max(dp[step], dp[next]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> k;
    int u, v;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    search(u, -1, 0);
    t2 = t1;
    search(t1, -1, 0);
    int mid = t1;
    for (int i = 1; i <= (maxi + 1) / 2; i++) {
        mid = root[mid];
    }
    dfs(mid, -1, 0);
    for (int i = 1; i <= n; i++) {
        ans[i] = dp[i] - dis[i];
    }
    sort(ans + 1, ans + n + 1, greater<int>());
    cout << ans[k + 1] + 1;
    return 0;
}