首页 > 其他分享 >AcWing. 1072 树的最长路径

AcWing. 1072 树的最长路径

时间:2023-01-16 15:37:17浏览次数:42  
标签:le dist qquad 路径 1072 距离 枚举 AcWing

题目描述

给定一棵树,树中包含 \(n\) 个结点(编号\(1\)~\(n\))和 \(n-1\) 条无向边,每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说,要找到一条路径,使得使得路径两端的点的距离最远。

注意:路径中可以只包含一个点。

解题思路

\(\qquad\)首先因为是树所以有这样的一个性质:树上两点之间有且仅有一条路径,路径\((x,y)\)可以拆分成两条路径 \((x,r)\) 和 \((r,y)\),其中 \(r\) 表示 \(LCA(x, y)\)。

\(\qquad\)所以我们可以得到一个思路:枚举断点 \(r\),状态 \(dist[r]\) 表示 \(r\) 的子树中,与 \(r\) 距离最远的点的距离。对于 \(r\) 的所有子节点 \(x_1, x_2, x_3,......x_k\),有

\[\Large dist[r] = \max_{1\le i\le k}\{ dist[x_i] + w(r,x_i)\} \]

\(\qquad\) 然后再定义 \(f[x]\) 为以 \(x\) 为断点的最长链,那么树的直径就是

\[\Large \max_{1\le x\le n}\{f[x]\} \]

求\(f\)的过程如下图所示
切格瓦拉.png
对于 \(x\) 的任意两个子节点 \(y_i\) 和 \(y_j\),\(f[x]\) 可以分成下面四个部分的和
\(\qquad 1.\) 从 \(y_i\) 到 \(y_i\) 的子树的最大距离
\(\qquad 2.\) 从 \(y_i\) 到 \(x\) 的距离
\(\qquad 3.\) 从 \(x\) 到 \(y_j\) 的距离
\(\qquad 4.\) 从 \(y_j\) 到 \(y_j\) 子树的最大距离
因此$$\large f[x] = \max_{1\le j<i\le k}{{dist[y_i] + dist[y_j] + w(x,y_i) + w(x,y_j) }}$$

然后就OK了

优化

如果我么顺序枚举,那么在将要枚举到 \(i\) 的时候,对于每个已经枚举过的节点 \(j < i\) 我们都可以保存到从 \(x\) 出发走向以 \(y_j\) 为根的子树最大距离,这个距离也就是

\[\large \max_{1\le j < i}\{dist[y_j] + w(x,y_j)\} \]

所以我们可以一边枚举一边用\(dist[x] + dist[y_i] + w(x, y_i)\) 更新 \(f[x]\), 一边用\(dist[y_i] + w(x, y_i)\) 更新 $ dist[x]$。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = N << 1;
int h[N], e[M], w[M], ne[M], idx = 1;
bool st[N]; int n, dist[M], res = -0x3f3f3f;

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

void dp(int x)
{
    st[x] = true;
    for (int i = h[x]; ~i; i = ne[i]) 
    {
        int j = e[i];
        if (st[j]) continue ;
        dp(j);
        res = max(res, dist[x] + dist[j] + w[i]);
        dist[x] = max(dist[x], dist[j] + w[i]);
    }
    res = max(res, dist[x]);
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);

    while (n -- ) 
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }

    dp(1);
    printf("%d\n", res);

    return 0;
}

标签:le,dist,qquad,路径,1072,距离,枚举,AcWing
From: https://www.cnblogs.com/StkOvflow/p/17055459.html

相关文章