小A与欧拉路

小A与欧拉路

分析

• 欧拉路：

  该路径经过图的每一条边且仅经过一次。如果路径起点和终点相同，则称“欧拉回路”。具有欧拉回路的图称“欧拉图”。

• 即
  
  因为要求最短，那么path(x,y)最长即可。就是一个树的直径的模板

代码

/*树的直径*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=2e5+10;

int n,tot,ans,sum;
int h[N],nex[N<<1],ver[N<<1],pri[N];
int dis[N],f[N],g[N];

inline void add(int x,int y,int z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    pri[tot]=z;
    h[x]=tot++;
}

inline void dfs(int u,int v)
{
    f[u]=g[u]=0;
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        dfs(j,u);

        if(f[j]+pri[i]>f[u])
        {
            g[u]=f[u];
            f[u]=f[j]+pri[i];
        }
        else g[u]=max(g[u],f[j]+pri[i]);
    }
    ans=max(ans,f[u]+g[u]);
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);sum+=z;
    }

    dfs(1,0);

    printf("%lld\n",2ll*sum-(ll)ans);

    return 0;
}