题目描述

Description

Input

第一行是两个整数N（3  N  200000）和M，分别表示居住点总数和街道总数。以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1Ui, Vi  N，1  Ti  1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。街道信息不会重复给出。

Output

仅包含整数T，即最坏情况下Chris的父母需要花费T分钟才能找到Chris。

Sample Input

4 3
1 2 1
2 3 1
3 4 1

Sample Output

4

题目分析

实质上是一个点拉出三条链
令长度a>b>c 那么ans=c+a+2*b
然后我们枚举每个点作为分叉点 这三条链可以从子树里来 也可以从父树里来
那么愉快树形DP即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,tot;
int head[200010],net[400010],to[400010],fa[200010];
long long val[400010];
void add(int x,int y,int c) 
{ net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c; }
long long d1[200010],d2[200010],d3[200010],f[200010];
void dfs(int x)
{   
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==fa[x]) continue;
        fa[to[i]]=x,dfs(to[i]);
        d3[x]=max(d3[x],d1[to[i]]+val[i]);
        if(d3[x]>d2[x]) swap(d2[x],d3[x]);
        if(d2[x]>d1[x]) swap(d1[x],d2[x]);
    }
}
void dfs2(int x)
{   
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==fa[x]) continue;
        f[to[i]]=f[x]+val[i];
        if(d1[x]==d1[to[i]]+val[i]) 
            f[to[i]]=max(f[to[i]],d2[x]+val[i]);
        else f[to[i]]=max(f[to[i]],d1[x]+val[i]);
        dfs2(to[i]);
    }
}   
long long st[20],ans;
long long wo(long long dx,long long dy,long long dc,long long dz)
{
    st[1]=dx,st[2]=dy,st[3]=dc,st[4]=dz;
    sort(st+1,st+4+1);
    return st[3]*2+st[2]+st[4];
}
int main()
{   
    scanf("%d%*d",&n);
    for(int x,y,c,i=1;i<n;i++)
        scanf("%d%d%d",&x,&y,&c),add(x,y,c),add(y,x,c);
    dfs(1),dfs2(1);
    for(int i=1;i<=n;i++) ans=max(ans,wo(d1[i],d2[i],d3[i],f[i]));
    printf("%lld",ans);
    return 0;
}