逃学的小孩,树形dp

先找到题

题意：

　　中文题，没什么好解释的，也没什么歧义。

分析：

　　首先我们想一下他的路径将会是怎样的：A-B-C/A-C-B，其实就是求一下min（AB+BC，AC+BC），ABC任选。挺简单，首先证明一点：BC不是直径时不会更优，证明之后，我们就可以直接找到直径，然后遍历每个点，实在是有点简单了，也没啥细节。

　　还可以这么想：他的路径是这样的：A-O-B-O-C/A-O-C-O-B，及他是由三段组成的，枚举点O（可以理解成二次元换根，或者说就是两遍dfs）计算最长的三段，求max（ma1+ma2*2+ma3）就好了。也是过于简单。最后就是代码。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=+;

int head[maxn];

struct E{

    int to;

    int next;

    long long val;

    E(){

        to=next=val=;

    }

}ed[maxn*];

int tot;

void J(int a,int b,long long c){

    tot++;

    ed[tot].to=b;

    ed[tot].val=c;

    ed[tot].next=head[a];

    head[a]=tot;

}

long long ma1[maxn];

long long ma2[maxn];

long long ans;

int jl;

long long j1[maxn];//记录到两段的距离

long long j2[maxn];

int m1a[maxn];//记录节点

int m2a[maxn];

void Dfs1(int x,int fa){

    m1a[x]=m2a[x]=x;//初始化，

    int js=;

    for(int i=head[x];i;i=ed[i].next){

        if(ed[i].to==fa)

            continue;

        js++;

        Dfs1(ed[i].to,x);

        ma2[x]=max(ma2[x],ed[i].val+ma1[ed[i].to]);

        if(ma2[x]==ed[i].val+ma1[ed[i].to])

            m2a[x]=m1a[ed[i].to];

        if(ma2[x]>ma1[x]){

            swap(ma2[x],ma1[x]);

            swap(m2a[x],m1a[x]);

        }

    }

    ans=max(ma1[x]+ma2[x],ans);

    if(ma1[x]+ma2[x]==ans)

        jl=x;

    if(!js)

        m1a[x]=m2a[x]=x;

}

void Dfs2(int x,int fa){

    for(int i=head[x];i;i=ed[i].next){

        if(ed[i].to==fa)

            continue;

        j1[ed[i].to]=j1[x]+ed[i].val;

        Dfs2(ed[i].to,x);

    }

}

void Dfs3(int x,int fa){

    for(int i=head[x];i;i=ed[i].next){

        if(ed[i].to==fa)

            continue;

        j2[ed[i].to]=j2[x]+ed[i].val;

        Dfs3(ed[i].to,x);

    }

}

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    int js1,js2;

    long long js3;

    for(int i=;i<=m;i++){

        scanf("%d%d%lld",&js1,&js2,&js3);

        J(js1,js2,js3);

        J(js2,js1,js3);

    }

    Dfs1(,);

    Dfs2(m1a[jl],);

    Dfs3(m2a[jl],);

    long long p=;

    for(int i=;i<=n;i++)

        p=max(p,min(j1[i],j2[i])+ans);

    printf("%lld",p);

    return ;

}