树的直径。
比赛的时候想着先树$dp$处理子树上的最长链和次长链，然后再从上到下进行一次$dfs$统计答案，和$CCPC$网络赛那个树$dp$一样，肯定是可以写的，但会很烦.......后来写崩了。
然后有一种新思路，很容易写。
假设下图中红线是树的直径，圆圈是直径上的节点，黑线表示一颗树。
如果删除的边不在直径上，那么删除这条边的答案就是直径长度。
如果删除的边在直径上，也就把下面的图分成了两半，左边和右边。
左边最大值会在什么情况下产生？
必然是$A->B->C$这样的情况产生的。不可能是从$D$到$C$这样的路径产生，因为$D->E$的长度最长只可能是$A->D$的长度。
右边部分最大值产生的情况也是一样的。
所以只要递推一下就可以了。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=x*+c-''; c=getchar();}
} const int maxn=;
int T,n,h[maxn],sz,mx,p1,p2,ll;
int path[maxn],tmp[maxn],cnt,ans[maxn];
struct Edge{int u,v,w,nx;}e[*maxn];
int M[maxn];
bool f[maxn],g[maxn];
int P[maxn],Q[maxn],li[maxn],num; void add(int a,int b,int c)
{
e[sz].u=a; e[sz].v=b; e[sz].w=c;
e[sz].nx=h[a]; h[a]=sz++;
} void dfs(int x,int dep,int len,bool d)
{
f[x]=;
if(len>mx)
{
if(d==) mx=len,p1=x;
else
{
mx=len,p2=x,cnt=dep;
for(int i=;i<cnt;i++) path[i]=tmp[i];
}
}
for(int i=h[x];i!=-;i=e[i].nx)
{
if(f[e[i].v]) continue;
tmp[dep]=i;
dfs(e[i].v,dep+,len+e[i].w,d);
}
} void Find(int x,int len)
{
g[x]=; if(len>ll) ll=len;
for(int i=h[x];i!=-;i=e[i].nx)
{
if(f[i/]) continue;
if(g[e[i].v]) continue;
Find(e[i].v,len+e[i].w);
}
} int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(h,-,sizeof h); cnt=sz=;
for(int i=; i<n-; i++)
{
int u,v,w; scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
memset(f,mx=,sizeof f); dfs(,,,);
memset(f,mx=,sizeof f); dfs(p1,,,); // for(int i=0;i<cnt;i++) printf("%d -> %d\n",e[path[i]].u,e[path[i]].v); memset(f,,sizeof f);
for(int i=; i<cnt; i++) f[path[i]/]=; memset(g,,sizeof g); int L=,R; for(int i=;i<cnt;i++)
{
ll=; Find(e[path[i]].v,);
M[e[path[i]].v]=ll;
} L=; P[e[path[]].u]=;
for(int i=;i<cnt;i++)
{
L=L+e[path[i]].w;
P[e[path[i]].v]=max(L+M[e[path[i]].v],P[e[path[i]].u]);
} R=; Q[e[path[cnt-]].v]=;
for(int i=cnt-;i>=;i--)
{
R=R+e[path[i]].w;
Q[e[path[i]].u]=max(R+M[e[path[i]].u],Q[e[path[i]].v]);
} for(int i=;i<cnt;i++)
{
int x1=P[e[path[i]].u],x2=Q[e[path[i]].v];
ans[path[i]/]=max(x1,x2);
} for(int i=; i<n-; i++) if(f[i]==) ans[i]=mx; LL Ans=;
for(int i=;i<n-;i++) Ans=Ans+(LL)ans[i];
printf("%lld\n",Ans);
}
return ;
}