小A与欧拉路

在纸上画一棵树,发现如果是回路,每条边走两次就够了

那么不是回路,有些边就不需要走两次了

发现,任意选择两点,从端点出发,路上一旦出现分支就出去走两遍回来

这样走到两一个端点的时候,两点间的距离其实只被走了一次

这样的话就求树的直径就好了

有点像规律题呢

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5+10;
int n,ans,temp;
struct edge{
    int to,nxt,w;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int w){
    d[++cnt] = (edge){v,head[u],w},head[u]=cnt;
}
//f表示最大,ci表示次大
int f[maxn],ci[maxn]; 
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==fa )    continue;
        dfs(v,u);
        if( f[v]+d[i].w>=f[u] )
            ci[u] = f[u],f[u] = f[v]+d[i].w;     
        else if( ci[u]<f[v]+d[i].w )
            ci[u] = f[v]+d[i].w;
    }
}
void DP(int u,int fa)
{
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v== fa)    continue;
        if( f[u]==f[v]+d[i].w )
            temp = max( temp,ci[u]+f[v]+d[i].w );
        else 
            temp = max( temp,f[u]+f[v]+d[i].w );
        DP(v,u);
    }
}
signed main()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int l,r,w; cin >> l >> r >> w;
        add(l,r,w); add(r,l,w);
        ans += w*2;
    }
    dfs(1,0);
    DP(1,0);
    cout << ans-temp;
}