洛谷比赛 U5442 买(最长链)

/*

这题可以证明是求边权之和*2-最长链.

bfs从根的左树和右树分别跑最长链取大.

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define MAXN 50001

using namespace std;

int head[MAXN],n,m,cut,ans,maxans,ans1,ans2,maxt,dis[MAXN],tot,fa[MAXN],tot1,tot2;

struct data{int v,next,x;}e[MAXN*2];

bool b[MAXN];

int read1()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,int z)

{

    e[++cut].v=v;

    e[cut].next=head[u];

    e[cut].x=z;

    head[u]=cut;

}

void dfs(int u,int f)

{

    fa[u]=f;

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].v;

        if(f!=v&&!fa[v])

        {

            if(u==1)

            {

                if(!tot1) tot1=v,ans1=e[i].x;

                else tot2=v,ans2=e[i].x;

            }

            tot+=e[i].x;

            dfs(v,u);

        }

    }

}

void spfa(int s)

{

    int u,v;

    memset(dis,-1,sizeof dis);

    memset(b,0,sizeof b);

    queue<int>q;q.push(s);dis[s]=0;

    while(!q.empty())

    {

        u=q.front();q.pop();b[u]=false;

        for(int i=head[u];i;i=e[i].next)

        {

            v=e[i].v;

            if(v==1) continue;

            if(dis[v]==-1)

            {

                dis[v]=dis[u]+e[i].x;

                if(dis[v]>ans)

                {

                    ans=dis[v];

                    maxt=v;

                }

                if(!b[v]) b[v]=true,q.push(v);

            }

        }

    }

}

int main()

{

    int x,y,z;

    n=read1();

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

    {

        x=read1(),y=read1(),z=read1();

        add(x,y,z);add(y,x,z);

    }

    dfs(1,1);

    spfa(tot1);

    ans+=ans1;

    maxans=max(maxans,ans);

    ans=0;spfa(tot2);ans+=ans2;

    maxans=max(maxans,ans);

    printf("%d",2*tot-maxans);

    return 0;

}