树的中心（树形dp）

68 阅读 0 评论 45 点赞

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

概述

在这里插入图片描述

思路：要找一个最大距离最小的点，那么有2个方向1.这u点下面最远距离2.这个u点上面的最远距离，这里向上走有2种走法，一直是直接求u点的子节点没有访问过求向上和向下的最大值，访问过则求向上最大值和向下次大值的最大值，这里需要记录一下路径用p1[i]记录最大距离从i经过的话是由那个点过来的，p2[i]记录次大。

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<iomanip>
#include<cstring>
#include<time.h>

using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
const int mod=1e9+7;
const int N=2e6+10;
const int M=1e3+10;
const int inf=0x3f3f3f3f;
const int maxx=2e5+7;
const double eps=1e-6;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
    return a*(b/gcd(a,b));
}

template <class T>
void read(T &x)
{
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-')
            op = 1;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op)
        x = -x;
}
template <class T>
void write(T x)
{
    if(x < 0)
        x = -x, putchar('-');
    if(x >= 10)
         write(x / 10);
    putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{
    ll res=1%p;
    while(b)
    {
        if(b&1)
            res=res*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return res;
}
int n;
struct node
{
    int to,nex,w;
}edge[N];
int head[N],tot;
int d1[N],d2[N],up[N];
int p1[N],p2[N];
void add(int u,int v,int w)
{
   edge[++tot].to=v;
   edge[tot].w=w;
   edge[tot].nex=head[u];
   head[u]=tot;
}
int ans=inf;
int dfs1(int u,int fa)
{
  
   // cout<<u<<' '<<fa<<endl;
     d1[u]=-inf;
     d2[u]=-inf;//最长距离和次长距离
    for(int i=head[u];~i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        int d=dfs1(v,u)+edge[i].w;
        if(d>=d1[u]){
            d2[u]=d1[u],d1[u]=d;
            p2[u]=p1[u],p1[u]=v;
        }
        else if(d>d2[u]) d2[u]=d,p2[u]=v;
    }
    if(d1[u]==-inf) d1[u]=d2[u]=0;
   // cout<<d1[u]<<endl;
    return d1[u];
    
}
void dfs2(int u,int fa)
{
    for(int i=head[u];~i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(v==fa)continue;
        if(p1[u]==v)up[v]=max(up[u],d2[u])+edge[i].w;
        else up[v]=max(up[u],d1[u])+edge[i].w;
        dfs2(v,u);
    }
}
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);
    }
    dfs1(1,-1);
    dfs2(1,-1);
    int res=inf;
    for(int i=1;i<=n;i++) res=min(res,max(up[i],d1[i]));
    cout<<res<<endl;

   
    return 0;
}