AcWing1073. 树的中心（树形dp）

60 阅读 0 评论 40 点赞

我是靠谱客的博主高高滑板，最近开发中收集的这篇文章主要介绍AcWing1073. 树的中心（树形dp），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：树的中心
LT’s blog
题意：找一个点，使得他到其他点的最长距离最小，边权有正有负。
最开始的时候我想这个点一定在树的直径上的中点位置处，WA了好多次后注意到题目数据范围，把这个思路直径否决了。
如果我们将这颗树化为一个有根树，那么一个点到其他点的最远距离就是：MAX(他到子树某个点的最远距离，他经过父亲节点到其他的点的最远距离)。
第一部分可以直接一次dfs得到，对于第二部分来说可以再次dfs维护数组F[u]，表示u经过父节点到其他节点的最远距离，由于他可能通过父节点走回自己(父节点到当前节点距离最远)，故在第一次dfs时候需要维护一个次大值，并且维护当前点是否在最长路径中。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e4+7;
vector<pair<int,int> > G[maxn];

void add(int u,int v,int w){
    G[u].push_back({v,w});
    G[v].push_back({u,w});
}

int FMax[maxn],SMax[maxn],neber[maxn];
int Up[maxn];
const int inf=0x3f3f3f3f;
void dfs(int u,int fa){
    FMax[u]=SMax[u]=-inf;
    for(auto p:G[u]){
        int v=p.first,w=p.second;
        if(v==fa) continue;
        dfs(v,u);
        int val=FMax[v]+w;
        if(val>=FMax[u]){
            SMax[u]=FMax[u];
            FMax[u]=val;
            neber[u]=v;
        }
        else SMax[u]=max(SMax[u],val);
    }
    if(FMax[u]==-inf) FMax[u]=SMax[u]=0;
}

void Dfs(int u,int fa){
    for(auto p:G[u]){
        int v=p.first,w=p.second;
        if(v==fa) continue;
        if(neber[u]==v) Up[v]=max(Up[u],SMax[u])+w;
        else Up[v]=max(Up[u],FMax[u])+w;
        Dfs(v,u);
    }
}
int main(){
    int n,u,v,w;
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    dfs(1,0);
    Dfs(1,0);
    int res=inf;
    for(int i=1;i<=n;++i) res=min(res,max(Up[i],FMax[i]));
    printf("%dn",res);

    return 0;
}