题目链接：蓝桥杯省赛-1207. 大臣的旅费

题目来源：第四届蓝桥杯省赛C++A组

题解：

本题用到了许多知识！下面给出参考教程及必备知识！

链式前向星：我的简单总结！点击这里！

树的直径及树形DP：秦淮岸灯火阑珊大佬的数的直径及树形DP讲义！点击这里！

秦淮岸大佬讲义对应视频：点击这里！

两次BFS搜索：DaulFrank大佬的两次BFS搜索！点击这里！

两次DFS搜索：小呆呆大佬的两次DFS搜索！点击这里！

两次搜索与树形DP区别：

  • 两次搜索可以求出数的直径的路径与值！写起来略麻烦！
  • 树形DP仅仅可以求出值！写起来简单！

知识积累一：树的直径

首先先引入圆的直径：

圆的直径就是圆上两点连线的最长的时候，所以树的直径就是树上最远两个点的距离！

官方解释：

在一棵树中，每一条边都有权值，树中的两个点之间的距离，定义为连接两点的路径上边权之和，那么树上最远的两个点，他们之间的距离，就被称之为，树的直径。

树的直径的别称，树的最长链。

请注意：树的直径，还可以认为是一条路径，不一定是只是一个数值。

稍做解释：

  • 当树的边权都为1或者没有边权时，即为树的最长连
  • 当树的边权不都为1时，树的直径为一条路径上的边权之和最大的那条

知识积累二：树形DP

主要用来求树的直径！

树形DP定义：

设1号节点为根节点，那么一张N个点，N−1条边的无向图,我们可以认为它是一棵有根树。

我们不妨设dis[x]表示从节点x出发，以x为根的子树，能过到达最远节点的距离。

也就是对于x节点而言的最长链。（**注意：**此处x到达的只能是孩子节点，不能到达父节点）

做一个规约：

父节点为 x 子节点为 y

dis[x]表示从x节点出发的最长链的边权和

ver[i]表示以i为终点的边权

res 表示树的直径，即最大的边权之和

接下来继续：

状态表示： dis[x] 含义见上面！

转态计算：dis[x] = max(dis[x], dis[y] + ver[i])

简单解释：从x出发的最长链 = 从儿子节点出发的最长链 + 父亲到儿子的距离 并且最后取一个最大值（即找一边权和最大的）

再看此时的数的直径如何计算？

**先给出结论：数的直径 = 最长链 + 次长链 即 res = max(res, dis[x] + dis[y] + ver[i]); **

简单解释： 从一个节点出发的最长链和次长链的和就是一条待选择的，所有节点的最长链和次长链的和的最大值即为树的直径！

对于最长链和次长链的两种情况：

  • dis[x] < dis[y] + ver[i]：即当前儿子的路径更长，由于原来最长为dis[x]，现在儿子最长，则最长链：dis[y] + ver[i]； 次长链为：dis[x]
  • dis[x] > dis[y] + ver[i]：即当前儿子的路径不如父亲长，此时：最长链：dis[x] 次长链：？dis[y] + ver[i]是吗？不是的，此时的儿子还不一定遍历完了，所以，此时的儿子这条路径可能为第二长，第三长 …

对于第一种情况：res = dis[x] + dis[y] + ver[i]

对于第二种情况：res = dis[x] + dis[y] + ver[i] （虽然此时的儿子路径不一定是次长，但是后面遍历的过程会逐渐更新）

此时的y指的是x的所有儿子节点，所以最终数的直径为：res = max(res, dis[x] + dis[y] + ver[i])

注意点：

下面代码顺序不能换，一定要先搜索到根节点，然后先更新树的直径，再更新父节点的边权！

后两句顺序反了会导致父节点先更新，答案树的直径逻辑就不对了！

1
2
3
dp(y);
res = max(res, dis[x] + dis[y] + ver[i]);
dis[x] = max(dis[x], dis[y] + ver[i]);

模板：树的直径

下面的例题就是树的直径模板题！

代码见 AC代码一 ！

题目简述：

给定n个节点，n - 1条边的带权无向图，问从一个节点到另一个节点的最大边权之和的路径的路费！

对于路费：如果边权之和为1 则路费为11 边权和为 2 路费为 11 + 12 …类似 即 11 + 12 + 13 + 14…

题解一：树形DP

有了上面两个知识积累，会发现这个题就是让你求数的直径，然后将数的直径转换为路费即可！

对于路费：是一个以11为首相，1为公差，项数为树的直径的等差数列，求和公式为 res * 11 + res * (res - 1ll) / 2

注意：

  • 防止结果溢出，使用1ll强转一下
  • 无向图，需要正反存储两次边
  • 正反存储两次边，所以对于链式前向星存储，每条边的编号tot的范围为 2 * (n - 1) 一条边需要两个编号（正反向），所以edge ver Next数组都是2倍空间！
  • 注意链式前向星head数组的初始化，即最开始邻接表都指向-1

时间复杂度： $O(n)$

AC代码一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;
int head[N], edge[N * 2], ver[N * 2], Next[N * 2], n, tot;
int vis[N], dis[N], res;

void add(int u, int v, int w)
{
    edge[tot] = v;
    ver[tot] = w;
    Next[tot] = head[u];
    head[u] = tot++;
}

void dp(int x)
{
    vis[x] = 1;
    for(int i = head[x]; ~i; i = Next[i]){
        int y = edge[i];
        if(vis[y]) continue;
        dp(y);
        res = max(res, dis[x] + dis[y] + ver[i]);
        dis[x] = max(dis[x], dis[y] + ver[i]);
    }
}

int main()
{
    cin >> n;
    memset(head, -1, sizeof head);
    for(int i = 0; i < n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dp(1);
    printf("%lld\n", res * 11 + res * (res - 1ll) / 2);
    return 0;
}

知识积累三：两次搜索

两次搜索思量：

  • 随便选一点x开始搜索，找到离当前点最远的y
  • 从y开始搜索，找到离当前节点最远的z
  • y到z的路径就是树的直径！

由于是搜索，是可以记录路径的！

证明： y一定是树的直径的一个端点

仍然使用反证法：

假设：y不是树的直径的一个端点，且 u - v 为树的直径！

默认条件： 离 x 最远的节点为 y

情况一： x - y 与 u - v 有交点，且 离 x 最远的节点为 y，则：

1
2
3
4
5
1 + 4 >= 1 + 3
即 3 <= 4
3 + 2 <= 4 + 2
即 u - v 不一定最长
若u - v 为直径，则u - y, v - y 都是直径，与假设矛盾， 即y一定是树的直径的一个端点！

情况二： x - y 与 u - v 没有交点，且 离 x 最远的节点为 y，则：

1
2
3
4
5
6
1 + 2 >= 1 + 3 + 5
即 2 >= 3 + 5
2 + 3 > 5
2 + 3 + 4 > 5 + 4
即 u - v 一定不是最长
与假设矛盾，从y出发一定有比 u - v更长的路径，如 2 - 3 - 4 、2 - 3 - 5

终上所述： 从一个点搜索到距离最远的点，改点一定是树的直径的一个端点！

从树的直径出发搜一个最远的点，一定是树的直径！

题解二：两次DFS搜索

使用DFS搜索：两种方法，建议使用第二种，少开辟一个数组，并且减少一次初始化操作！

  • void dfs(int x, int distance) ：参数为父节点和当前已经累积的距离
  • void dfs(int x, int father, int distance)：参数为父节点和当前节点的父节点，以及当前已经累积的距离

搜索入口：dfs(1, -1, 0) 以1号边为根节点开始搜索，根节点没有父节点为-1

简单的思路：

  • 从根节点开始，往下搜索一个儿子就将当前儿子的权累加父节点，直到搜完节点，得到每个叶子节点从根到自己的权之和！
  • 遍历一次每个节点，找到从根节点最远的节点，即dis数组最大的那个节点的下标即可！
  • 再从当前最大权的节点搜索一次，找到离当前端点最远的节点即可！
  • 再次遍历一次每个及诶单，找到该最远的节点！
  • 等差求和

注意： 第二次搜索dis数组不需要初始化，因为下一次搜索会全部进行覆盖！

时间复杂度： $O(n)$

AC代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// 使用vis数组判断 第二次搜索需要初始化一次该数组

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;
int head[N], edge[N * 2], ver[N * 2], Next[N * 2], n, tot;
int vis[N], dis[N], res;

void add(int u, int v, int w)
{
    edge[tot] = v;
    ver[tot] = w;
    Next[tot] = head[u];
    head[u] = tot++;
}

void dfs(int x, int distance)
{
    dis[x] = distance;
    vis[x] = 1;
    for(int i = head[x]; ~i; i = Next[i]){
        int j = edge[i];
        if(vis[j]) continue;
        dfs(j, distance + ver[i]);
    }
}

int main()
{
    cin >> n;
    memset(head, -1, sizeof head);
    for(int i = 0; i < n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0);
    int u = 1;
    for(int i = 1; i <= n; i++)
        if(dis[i] > dis[u]) u = i;
        
    memset(vis, 0, sizeof vis);
    dfs(u, 0);
    for(int i = 1; i <= n; i++) res = max(res, dis[i]);
    
    printf("%lld\n", res * 11 + res * (res - 1ll) / 2);
    return 0;
}


/************************************************************************************************/
/************************************************************************************************/
// 不使用vis数组 使用father变量判断
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;
int head[N], edge[N * 2], ver[N * 2], Next[N * 2], n, tot;
int vis[N], dis[N], res;

void add(int u, int v, int w)
{
    edge[tot] = v;
    ver[tot] = w;
    Next[tot] = head[u];
    head[u] = tot++;
}

void dfs(int x, int father, int distance)
{
    dis[x] = distance;
    for(int i = head[x]; ~i; i = Next[i]){
        int y = edge[i];
        if(y == father) continue;
        dfs(y, x, distance + ver[i]);
    }
}

int main()
{
    cin >> n;
    memset(head, -1, sizeof head);
    for(int i = 0; i < n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dfs(1, -1, 0);
    int u = 1;
    for(int i = 1; i <= n; i++)
        if(dis[i] > dis[u]) u = i;
        
    dfs(u, -1, 0);
    for(int i = 1; i <= n; i++) res = max(res, dis[i]);
    
    printf("%lld\n", res * 11 + res * (res - 1ll) / 2);
    return 0;
}

题解三：两次BFS搜索

两次BFS搜索：

思路： 与两次DFS思想一致，走到儿子就更新儿子的权，下方BFS过程也是一个标准过程！

  • 先进行vis 和 dis数组的初始化
  • 随便一个节点进行搜索
  • 将当前节点假如队列，标记使用过
  • 出队列，将当前队首的所有没有访问过的儿子节点进队
  • 更新儿子节点的权为父节点权与当前路径之和，即 dis[y] = dis[x] + ver[i];
  • 为了减少最后的扫描，可以在其中进行统计最大权的下标max_i
  • 标记儿子用过，儿子入队
  • 队列为空结束
  • 从最大权的下标max_i开始第二次搜索找到树的直径的终点！
  • 等差求和

时间复杂度： $O(n)$

AC代码三：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// https://www.acwing.com/solution/content/7896/

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;
int head[N], edge[N * 2], ver[N * 2], Next[N * 2], n, tot;
int vis[N], dis[N], res;

void add(int u, int v, int w)
{
    edge[tot] = v;
    ver[tot] = w;
    Next[tot] = head[u];
    head[u] = tot++;
}

int bfs(int u)
{
    queue<int> q;
    memset(vis, 0, sizeof vis);
    memset(dis, 0, sizeof dis);
    int max_i;
    q.push(u);
    vis[u] = 1;
    while(q.size()){
        int x = q.front();
        q.pop();
        for(int i = head[x]; ~i; i = Next[i]){
            int y = edge[i];
            if(vis[y]) continue;
            dis[y] = dis[x] + ver[i];
            if(dis[y] > res){
                res = dis[y];
                max_i = y;
            }
            vis[y] = 1;
            q.push(y);
        }
    }
    return max_i;
}

int main()
{
    cin >> n;
    memset(head, -1, sizeof head);
    for(int i = 0; i < n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    int u = bfs(1);
    bfs(u);
    
    printf("%lld\n", res * 11 + res * (res - 1ll) / 2);
    return 0;
}