树的中心

树中心 DFS 树形dp

题目

1073. 树的中心 - AcWing题库

给定一棵树，树中包含 $n$ 个结点（编昊 $1\sim n$ ) 和 $n-1$ 条无向边，每条边都有一个权值。 请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

输入格式

第一行包含整数 $n$ 。 接下来 $n-1$ 行，每行包含三个整数 $a_i,b_i,c_i$ ，表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。

输出格式

输出一个整数，表示所求点到树中其他结点的最远距离。

数据范围

$1\le n\le 10000$ $1\le a_i,b_i\le n$ $1\le c_i\le 10^5$

样例

input

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

output

2

思路

可以采用枚举的方式, 计算出该点对于所有点的最大距离, 然后选择最小的那个点。 那么具体操作就是

1. 先DFS一遍用子节点更新父节点, 计算出所有往下走的最大值和次大值
2. 再DFS一遍用父节点更新子节点, 计算出所有往上走的路径, 若不经过该子节点则是最大值, 若经过则是次大值

转移方程就是：f[i] = max(up[i], down[i]), 计算up时需要判断当前往下走的最大值是否经过子节点, 则在求解down时就把最大值和次大值的路径保存下来。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e4 + 10, M = 2 * N, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int n;
int d1[N], d2[N], p1[N], p2[N], up[N]; // p1, p2记录最大值和次大值的路径
 
void add(int a, int b,int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
 
int dfs_d(int u, int fa)
{
    d1[u] = d2[u] = -INF;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        int d = dfs_d(j, u) + w[i];
        if(d >= d1[u])
        {
            d2[u] = d1[u];
            p2[u] = p1[u];
            d1[u] = d;
            p1[u] = j;
        }
        else if(d > d2[u])
        {
            d2[u] = d;
            p2[u] = j;
        }
    }
    
    if(d1[u] == -INF) d1[u] = d2[u] = 0;
    
    return d1[u];
}
 
void dfs_u(int u, int fa)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) 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_u(j, u);
    }
}
 
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a,b,c), add(b,a,c);
    }
    
    dfs_d(1,-1);
    dfs_u(1,-1);
    
    int res = INF;
    for(int i = 1; i <= n; i++)
    {
        res = min(max(up[i], d1[i]), res);
    }
    cout << res << endl;
    
    return 0;
}