传送门

一直在想怎么利用重心边来做,结果找不到什么结论,后来发现直接用重心就行了。。。

为了让总长最长,我们考虑每条边经过次数的上界,一定是两边子树大小的较小值*2。我们要尽量取到这个上界。

我们先找到树的重心。如果重心的某个儿子的大小达到了$n/2$,则重心到这棵子树的边只能经过$n-1$次,其他边经过次数都能达到上界。否则,我们可以证明,在重心连出去的所有边中,肯定至少有一条边达不到上界。同时,我们也可以构造一种方案,使得只有一条重心连出的边走上界-1次,其他所有边都达到上界。所以找一下重心连出去的权值最小的边就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXN 100010
using namespace std;

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n;
int g[MAXN],nume;
int size[MAXN],maxs[MAXN];
LL ve[MAXN];

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void dfs(int x,int p){
    size[x]=1; maxs[x]=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            ve[e[i].to]=e[i].w;
            dfs(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>maxs[x]) maxs[x]=size[e[i].to];
        }
    if(n-size[x]>maxs[x]) maxs[x]=n-size[x];
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    dfs(1,0);
    LL ans=0;
    for(int i=2;i<=n;i++) ans+=2*ve[i]*min(size[i],n-size[i]);
    for(int i=2;i<=n;i++)
        if(size[i]==n-size[i]){
            ans-=ve[i];
            printf("%lld\n",ans);
            return 0;
        }
    int root=1;
    for(int i=1;i<=n;i++)
        if(maxs[i]<maxs[root]) root=i;
    int temp=0x7FFFFFFF;
    for(int i=g[root];~i;i=e[i].next)
        if(e[i].w<temp) temp=e[i].w;
    ans-=temp;
    printf("%lld\n",ans);
    return 0;
}