快乐树论

Description

 曾经有一位伟大的皇帝，他拥有n座城池并用n-1条无向道路相连，每条道路均有一个确定的长度和两个端点，保证城池与城池之间互达。有一天，皇帝决定将其中一条路拆掉，并重新将这条道路以同样的长度搭在两座城池之间，皇帝可能将这条路拆了又重新建在原处。现在皇帝想问问你，在只拆掉一条道路并重新建造一条同样长的在两座城池之间后，任意两个城池之前的距离和最小为多少呢？

Input

 第一行输入一个n代表皇帝有n座城池，接下来n-1行输入a,b,c代表城池a,b之间有一条长为c的道路。 (2 ≤ n ≤ 5000, 1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 106)

Output

 输出一行任意两城池之间的最小距离和。

Sample Input

输入样例1： 3 1 2 2 1 3 4 输入样例2： 6 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 输入样例3： 6 1 3 1 2 3 1

Sample Output

输出样例1： 12 输出样例2： 29 输出样例3： 825

HINT

 实际输入输出中并没有“输入样例1”， “输出样例1：” 之类 这种东西，这里只是为了多给几组数据，让大家更容易的理解用的

题解：

具体证明参考：https://blog.csdn.net/zhoufenqin/article/details/9821617

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll,ll> Pll;

const ll LLMAX=2e18;
const int MAXN=1e6+10;

struct node{
    int u,v;
    ll w;
}in[MAXN];

ll dp[MAXN][3];
vector<Pll>G[MAXN];

void dfs(int u,int pre){
    dp[u][0]=dp[u][1]=dp[u][2]=0;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].fi,w=G[u][i].se;
        if(v==pre)   continue;
        dfs(v,u);
        dp[u][2]+=dp[v][2]+dp[v][1]*dp[u][0]+dp[v][0]*dp[u][1]+dp[u][0]*dp[v][0]*w;
        dp[u][1]+=dp[v][1]+dp[v][0]*w;
        dp[u][0]+=dp[v][0];            
    }
    dp[u][0]++;
    dp[u][2]+=dp[u][1];
}

void solve(int u,int pre,ll &ans){
    ans=min(ans,dp[u][1]);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].fi,w=G[u][i].se;
        if(v==pre)  continue;
        dp[v][1]=dp[v][1]+(dp[u][1]-dp[v][1]-w*dp[v][0])+(dp[u][0]-dp[v][0])*w;
        dp[v][0]=dp[u][0];
        solve(v,u,ans);
    }
}

int main(void)
{
    ios::sync_with_stdio(false);    cin.tie(0);
    ll n,ans=LLMAX;  cin>>n; 
    for(int i=1;i<n;i++){
        ll x,y,v;  cin>>x>>y>>v;    
        in[i].u=x,in[i].v=y,in[i].w=v;
        G[x].pb(Pll(y,v)),G[y].pb(Pll(x,v));
    }
    for(int i=1;i<n;i++){
        ll ans1=LLMAX,ans2=LLMAX,u=in[i].u,v=in[i].v,w=in[i].w;
        dfs(u,v);   solve(u,v,ans1);
        ll len1=(n-dp[u][0])*ans1+dp[u][2];
        dfs(v,u);   solve(v,u,ans2);
        ll len2=(n-dp[v][0])*ans2+dp[v][2];
        ans=min(ans,len1+len2+dp[u][0]*dp[v][0]*w);
    }
    cout<<ans<<endl;
    return 0;
}