[AtCoder Grand Contest 018] D: Tree and Hamilton Path (agc018D)

原题链接
​​​https://agc018.contest.atcoder.jp/tasks/agc018_d​​

Description

给出一棵N个点带边权的树

现在有一个N个点的完全图，一条边x,y的长度是这两点的在树上最短路长度

求这个完全图的最长汉密尔顿路径（即从任意点开始将每个点访问且仅访问一次的路径）长度

N<=100000
边权<=1e8

Solution

如果想按顺序DP那就很麻烦了

考虑树上每条边对答案的贡献

我们希望答案尽量大，那就是树上的边尽可能被完全利用
即最好是这条边两侧一边一个一边一个

那么答案很显然就是每条边边权*两侧点数的最小值*2

如何构造这么一种方案？

绕着重心跑
每次访问重心的和上次不同的子树就行了

注意这样重心要么是第一个访问的，要么是最后一个访问的

那么与重心相连的某条边只会算一次

如果只有一个重心那么减掉最小那个就行了

有两个重心的话就减掉两个重心相连那条边

Code

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define LL long long
using namespace std;
int fs[N],nt[2*N],dt[2*N],n,m,sz[N],mw,mi,m2;
LL pr[2*N],ans;
void link(int x,int y,int z)
{
    nt[++m]=fs[x];
    dt[fs[x]=m]=y;
    pr[m]=z;
}
void dfs(int k,int fa)
{
    sz[k]=1;
    int mx=0;
    for(int i=fs[k];i;i=nt[i])
    {
        int p=dt[i];
        if(p!=fa)
        {
            dfs(p,k);
            sz[k]+=sz[p];
            mx=max(mx,sz[p]);
            ans+=(LL)min(sz[p],n-sz[p])*pr[i]*(LL)2;
        }
    }
    if(max(mx,n-sz[k])==mi) m2=k;
    if(max(mx,n-sz[k])<mi) mi=max(mx,n-sz[k]),mw=k,m2=0;
}
int main()
{
    cin>>n;
    mi=n;
    fo(i,1,n-1)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        link(x,y,z),link(y,x,z);
    }
    dfs(1,0);
    if(m2==0) 
    {
        mi=1802201963;
        for(int i=fs[mw];i;i=nt[i]) mi=min(mi,(int)pr[i]);
        ans-=mi;
    }
    else
    {
        for(int i=fs[mw];i;i=nt[i])
        {
            if(dt[i]==m2) 
            {
                ans-=pr[i];
                break;
            }
        }
    }
    printf("%lld\n",ans);
}