The great Shaass is the new king of the Drakht empire. The empire has n cities which are connected by n?-?1 bidirectional roads. Each road has an specific length and connects a pair of cities. There's a unique simple path connecting each pair of cities.
His majesty the great Shaass has decided to tear down one of the roads and build another road with the same length between some pair of cities. He should build such road that it's still possible to travel from each city to any other city. He might build the same road again.
You as his advisor should help him to find a way to make the described action. You should find the way that minimize the total sum of pairwise distances between cities after the action. So calculate the minimum sum.
Input
The first line of the input contains an integer n denoting the number of cities in the empire, (2?≤?n?≤?5000). The next n?-?1 lines each contains three integers ai, bi and wi showing that two cities ai and bi are connected using a road of length wi, (1?≤?ai,?bi?≤?n,?ai?≠?bi,?1?≤?wi?≤?106).
Output
On the only line of the output print the minimum pairwise sum of distances between the cities.
Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.
Examples
Input
3 1 2 2 1 3 4
Output
12
Input
6 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1
Output
29
Input
6 1 3 1 2 3 1 3 4 100 4 5 2 4 6 1
Output
825
#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<queue>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define mod 1e9+7
#define ll unsigned long long
#define INF 1000000000
#define ms memset
#define maxn 5005
using namespace std;/*
题目大意:给定一颗树，
要求可以拆掉一条边，
并且在分开的两个连通集中用该边的权重重建，
问最小的所有点路径和是多少。这道题目超出 我能力范围太多了，
看题解也看的磕磕绊绊，
但总算道理可以讲明白了。首先通过树形DP维护三个东西，
子树节点数量，子树所有点到根节点距离和，子树任意两点距离和，
注意这三个变量是互相关联的，暗含数学公式，
最困难的是第三个，在树形DP递归的过程中，求解第三个时
还要套一层DP思想，并且三者求解的顺序不能错。先利用没有更新当前子树的节点数量来DP任意两点距离和，
再更新子树所有点到根节点距离和，（利用求得的子树节点数量），
再次更新节点数量的DP。假设有了这三种，那么下面分析，
对拆的边进行枚举，
每次拆边树肯定分成了两个子树，那么对于这样的情况，如何选择两个点使得目标值最小呢？
很显然，我们选的两个点在相应的子树中，
都要满足所有子树点到该节点距离和最小的条件。
这就可以利用三个状态再次树形DP递归得到，即最小的所有点到该点距离和。详见代码（代码还是有点小问题，，能力有限，日后有时间修改，但思路是无误的）*/struct node///链式前向星板子
{int nxt;int e;ll w;node(int x=0,int y=0,ll z=0){e=x;nxt=y;w=z;}
};
node edge[maxn];
int head[maxn],tot=0;
void init(){memset(head,-1,sizeof(head));tot=0;}
void add(int a,int b,ll c){edge[tot]=node(b,head[a],c);head[a]=tot++;}ll n,dp[maxn][3];///0代表子树的节点数，1代表子树中所有点到根节点的路径之和，2代表子树中任意点对距离和。
void dfs(int u,int p)
{memset(dp[u],0,sizeof(dp[u]));if(head[u]==-1) {dp[u][0]=1;return ;}for(int i=head[u];~i;i=edge[i].nxt){int v=edge[i].e;if(v==p) 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]*edge[i].w;///又是一个线性的动态规划dp[u][1]+=dp[v][1]+dp[v][0]*edge[i].w;dp[u][0]+=dp[v][0];///子树的顶点数}dp[u][0]++;dp[u][2]+=dp[u][1];///
}void Find(int u,int pre,ll& record)///在子树中找到一个点，这个点到所有点距离和最小
{record=min(dp[u][1],record);for(int i=head[u];~i;i=edge[i].nxt){int v=edge[i].e;if(v==pre) continue;dp[v][1]=dp[v][1] + (ll)(dp[u][0]-dp[v][0])*edge[i].w+(dp[u][1]-dp[v][1]-dp[v][0]*edge[i].w);dp[v][0]=dp[u][0];Find(v,u,record);}
}int a[maxn],b[maxn];
ll c[maxn];int main()
{init();scanf("%lld",&n);for(int i=1;i<n;i++){scanf("%d%d%lld",&a[i],&b[i],&c[i]);add(a[i],b[i],c[i]);add(b[i],a[i],c[i]);}ll mi=INF,ans=INF,ret;for(int i=1;i<n;i++){mi=INF;dfs(a[i],b[i]);Find(a[i],b[i],mi);ll s1=(ll)(n-dp[a[i]][0])*mi+dp[a[i]][2];mi=INF;dfs(b[i],a[i]);Find(b[i],a[i],mi);ll s2=(ll)(n-dp[b[i]][0])*mi+dp[b[i]][2];ret=s1+s2+dp[a[i]][0]*dp[b[i]][0]*c[i];ans=min(ans,ret);///cout<<ret<<endl;}printf("%lld\n",ans);return 0;
}