AcWing 1073. 树的中心

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1073. 树的中心原题链接简单

作者：

辰风 , 2019-12-07 15:10:37 , 所有人可见 , 阅读 6771

98

30

思路

这是一道很好的树形dp题，即用到了用子节点更新父节点信息的普遍情况，又用到了用父节点更新子节点的情况，所以掌握这一道题是很有必要的，废话不多说，下面开始讲讲我对y总的思路的理解

首先分析题目，其实是要我们把每一个点到其他点的最长距离求出来，再求一个其中最短的就可以了，我们来分析一下每一个点可以再树上怎么走，其实就是向上和向下走

我们用 d1[u],d2[u],up[u],p1[u],p2[u]分别存一下需要的信息，这些数据存的是：
d1[u]：存下u节点向下走的最长路径的长度
d2[u]：存下u节点向下走的第二长的路径的长度
p1[u]：存下u节点向下走的最长路径是从哪一个节点下去的
p2[u]：存下u节点向下走的第二长的路径是从哪一个节点走下去的
up[u]：存下u节点向上走的最长路径的长度

向下走是很容易的，dfs就可以了，那怎么向上走呢？其实向上走就是求一个点的父节点的不走该节点的最长路径，其实我们知道了每一个节点向下走的长度就可以知道向上的最长路径了，一个子节点 j 的向上最长路径就是它的父节点 u 的最长向上路径和最长向下路径取最大值，如果向下最长路径经过了 j 就改为第二长的向下路径，对应代码：

 if(p1[u]==j)up[j]=max(up[u],d2[u])+w[i];
 else up[j]=max(up[u],d1[u])+w[i];

图有点丑.....
在这里插入图片描述

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+5,INF=1e9;
int d1[N];int d2[N];int up[N];int p1[N];int p2[N];int h[N];int ne[2*N];int e[2*N];int idx;
int w[N];
int n;
void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
int dfs_down(int u,int father){//返回u的最长向下路径
    d1[u]=d2[u]=-INF;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        int dist=dfs_down(j,u)+w[i];
        if(dist>d1[u]){//更新一下最长和第二长的路径，并记录下从该路径是从哪一个点下去的
            d2[u]=d1[u],d1[u]=dist;
            p2[u]=p1[u];p1[u]=j;
        }
        else if(dist > d2[u]){
            d2[u]=dist;
            p2[u]=j;
        }
    }
    if(d1[u]==-INF)d1[u]=d2[u]=0;//如果没有改变过该点的距离，就证明这个点是叶节点
    return d1[u];
}
void dfs_up(int u,int father){//用父节点更新一下子节点向上的最长路径
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        if(p1[u]==j)up[j]=max(up[u],d2[u])+w[i];//如果从父节点向下的最长路径进过了要更新的子节点，那么就用第二长的路径更新
        else up[j]=max(up[u],d1[u])+w[i];
        dfs_up(j,u);
    }
}
int main(){
    cin >> n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);add(b,a,c);
    }
    dfs_down(1,-1);
    dfs_up(1,-1);
    int res=INF;
    for (int i = 1; i <= n; i ++ ) res = min(res, max(d1[i], up[i]));
    cout << res;
}

36 评论

Empty_Sky 2023-05-02 21:34

图炸啦

Zhangwj 2022-09-09 20:23

怎么保证向下第二长的路径不经过j点

xaNe 2023-03-14 16:22

仔细看，dfs只返回了最大值，也就是说求出的次大值一定不是由那个子节点上来的

咸鱼翻身成牛马 5个月前回复了 xaNe 的评论

更新的时候，不是用d1去更新d2的吗，跟返回值有啥关系

Van_sama 2022-07-02 18:55

话说p2是需要的吗？

码农晋升中 2022-04-15 16:27

这个p2没用

南岸以南南岸哀 2022-05-29 16:56

确实，其实只要记录在不在当前节点在不在最长路径上就行，如果在就要用次长和向上距离更新，

Moriton 2023-05-04 19:40

用的记忆化搜索, ac了, 但是不知道这么做对不对, 以及是不是数据太弱, 有没有大佬愿意看一下我的代码

from sys import *
setrecursionlimit(100000)
N = 10010
M = 2 * N
e = [0] * M
ne = [0] * M
head = [-1] * N
w = [0] * M
idx = 0
f = {}
inf = float('inf')
def add(a, b, c):
    global idx
    e[idx] = b
    ne[idx] = head[a]
    head[a] = idx
    w[idx] = c
    idx += 1
def dfs(x, p):
    global n
    if (x, p) in f:
        return f[(x, p)]
    i = head[x]
    dis = 0
    while i != -1:
        j = e[i]
        if j == p:
            i = ne[i]
            continue
        dis = max(dis, dfs(j, x) + w[i])
        i = ne[i]
    f[(x, p)]= dis
    return dis
if __name__ == "__main__":
    n = int(stdin.readline())
    for i in range(n-1):
        a, b, c = map(int, stdin.readline().split())
        add(a, b, c)
        add(b, a, c)
    res = inf
    for i in range(1, n+1):
        res = min(res, dfs(i, 0))
    print(res)

LLMing 2023-01-26 22:35

j的父节点的向下次大距离不过j点晕了好久终于理解了。
dfs_u: 于其叫最大次大距离，不如叫”最大次大子树深度”即”以每个子树结点为根的树的长度”，这样求得的最大、次大、次次大都是过不同的子树的长度, 保证不过j点。
dfs_d: 枚举求当前u的每个子节点j的最大向上距离时，只需判断p1[u]!=j套用①中的向下最大次大距离更新；
最后比较每个结点的向上和向下距离最小的结点即可。

LLMing 2023-01-26 22:39

dfs_u和dfs_d标反了

在原七海Nanami 2022-11-09 23:13

如果d2和d1也经过当前点的话会影响结果吗
比如父节点u只有一条路走过来j

Icecream 2022-07-26 18:07

up[u]不太对啊

Hbzhtd 2022-07-05 10:44

up[j]=max(up[u],d2[u])+w[i]; 这里为啥要用up[u]来取max啊，直接用d2[u] + w[i]不行吗

糖豆 2023-03-06 11:20

不行啊，因为u其实有三条路线可以选择，up[u],d1[u],d2[u].

Mr.lonely_6 2022-04-03 12:13

发现很多题解都没有说清楚，光说数组的含义了。
这道题需要dfs两次的原因是：
第一次dfs是初始化每个点向下走可以到达的最远距离，但是还有一种情况没有考虑过，那就是向上走，而要求向上走的最大长度，我们必须用到父节点的值。父节点有很多分支，此时从父节点u开始走，但是不能回到子节点j，因为我们要求的是向上走.

potatoshi 2022-05-16 09:35

这边不是一个双向图吗，不是每个节点都可以当作根节点来看吗？？为什么还要向上呢？

天郁闷 2022-05-17 15:23 回复了 potatoshi 的评论

你要注意这一题和上一题的区别，上一题求的是 要找到一条路径，使得使得路径两端的点的距离最远 ,所以我们枚举的时候是把树中的每个节点当成根取枚举，然后每个节点上求的最大值和次大值用来更新答案。

注意这道题中 ``输出一个整数，表示所求点到树中其他结点的最远距离 , 因为权值都是正数，所以我们求的是每个节点到叶节点的最大距离。每个节点到叶子节点有2种方式，一种是向下走，一种是向上走。
然后每个节点到叶节点的最大距离是在max(d1[i], up[i])中产生

potatoshi 2022-05-17 19:34 回复了天郁闷的评论

你说的其实是一个意思我后来想通了是时间复杂度的问题不论是向上走还是向下走其实都是求得把这个节点当成根节点得到的最长路径

天郁闷 2022-05-17 20:05 回复了 potatoshi 的评论

这题根本就不是你说的求根节点的最长路径，看题目要求：输出一个整数，表示所求点到树中其他结点的最远距离 , 你说的把这个节点当成根节点得到的最长路径那是上一题的状态表示，这两道题是有区别的好吧。

天郁闷 2022-05-17 20:08 回复了 potatoshi 的评论

这两道题dp数组的含义都是不同的，这道题实际上求的应该是当前节点到其叶节点的最大值，然后再所有最大值中取一个最小值

potatoshi 2022-05-18 00:12 回复了天郁闷的评论

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = N << 1;
int h[N], e[M], w[M], ne[M], idx;

int n, f1[N], f2[N], res = 0x3f3f3f3f;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int dfs(int u, int father) {
    f1[u] = f2[u] = 0;
    for(int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if(j == father) continue;
        dfs(j, u);
        if(f1[j] + w[i] >= f1[u]) f2[u] = f1[u], f1[u] = f1[j] + w[i];
        else if(f1[j] + w[i] > f2[u]) f2[u] = f1[j] + w[i]; 
    }
    return f1[u];
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);

    for(int i = 0; i < n - 1; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    for(int i = 1; i <= n; i ++) res = min(res, dfs(i, -1));
    cout << res << endl;
    return 0;
}