模拟赛原题，应该是ybtoj上的

给定一棵 $N$ 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

思路是：

画图可以发现：对于任意两点之间要新建的边，其权值必定大于两点原有路径上的权值最大值

然后就是一个边转点树剖

但是莫名RE

#include<bits/stdc++.h>
using namespace std;
const int N=6005;
int n,TT,dep[N],son[N],top[N],id[N],rk[N],rr[N],fa[N],a[N],b[N],w[N],cnt,sz[N];
long long ans;
vector<int>v[N];
bool vis[N][N];
struct node{
	int l,r,val,tag;
};
struct Tree{
	node Tr[N<<2];
	#define ls(id) id<<1
	#define rs(id) id<<1|1
	inline void pushup(int id)
	{
		Tr[id].val=max(Tr[ls(id)].val,Tr[rs(id)].val);
		return;
	}
	inline void pushdown(int id)
	{
		if(Tr[id].tag!=-1)
		{
			Tr[ls(id)].val=Tr[rs(id)].val=Tr[id].tag;
			Tr[ls(id)].tag=Tr[rs(id)].tag=Tr[id].tag;
			Tr[id].tag=-1;
		}
		return;
	}
	inline void build(int id,int l,int r)
	{
		Tr[id]={l,r,0,-1};
		if(l==r)
		{
			Tr[id].val=w[rk[rr[l]]];
			return;
		}
		int mid=l+r>>1;
		build(ls(id),l,mid);
		build(rs(id),mid+1,r);
		pushup(id);
		return;
	}
	inline void modify(int id,int l,int r,int k)
	{
		if(l<=Tr[id].l&&Tr[id].r<=r)
		{
			Tr[id].tag=k;
			Tr[id].val=k;
			return;
		}
		pushdown(id);
		int mid=Tr[id].l+Tr[id].r>>1;
		if(l<=mid)modify(ls(id),l,r,k);
		if(r>mid)modify(rs(id),l,r,k);
		pushup(id);
		return;
	}
	inline int query(int id,int l,int r)
	{
		if(l<=Tr[id].l&&Tr[id].r<=r)
		{
			return Tr[id].val;
		}
		pushdown(id);
		int mid=Tr[id].l+Tr[id].r>>1,ans=0;
		if(l<=mid)ans=max(ans,query(ls(id),l,r));
		if(r>mid)ans=max(ans,query(rs(id),l,r));
		return ans;
	} 
}T;
inline void init()
{
	for(int i=1;i<=n;i++)
	{
		memset(vis[i],0,sizeof vis[i]);
		vector<int>().swap(v[i]);
	}
	if(n!=0)
	T.modify(1,1,n,0);
	T.Tr[1]={0,0,0,-1};
	ans=0;
	cnt=0;
	return;
}
inline void dfs1(int p,int faa)
{
	sz[p]=1;
	dep[p]=dep[faa]+1;
	fa[p]=faa;
	for(int t:v[p])
	{
		if(t==faa)continue;
		dfs1(t,p);
		sz[p]+=sz[t];
		if(sz[t]>sz[son[p]])son[p]=t;
	}
	return;
}
inline void dfs2(int p,int faa)
{
	top[p]=faa;
	id[p]=++cnt;
	rk[cnt]=p;
	if(!son[p])return;
	dfs2(son[p],faa);
	for(int t:v[p])
	{
		if(t==fa[p]||t==son[p])continue;
		dfs2(t,t);
	}
	return;
}
inline int query(int a,int b)
{
	int res=0;
	while(top[a]!=top[b])
	{
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		res=max(res,T.query(1,id[top[a]],id[a]));
		a=fa[top[a]];
	}
	if(dep[a]>dep[b])swap(a,b);
	res=max(res,T.query(1,id[a]+1,id[b]));
	return res;
}
int main()
{
	cin>>TT;
	while(TT--)
	{
		init();
		cin>>n;
		for(int i=1;i<=n-1;i++)
		{
			cin>>a[i]>>b[i]>>w[i+1];
			v[a[i]].push_back(b[i]);
			v[b[i]].push_back(a[i]);
			vis[a[i]][b[i]]=vis[b[i]][a[i]]=1;
		}
		dfs1(1,0);
		dfs2(1,1);
		for(int i=1;i<=n-1;i++)
		{
			if(dep[a[i]]<dep[b[i]])rr[i+1]=b[i];
			else rr[i+1]=a[i];
		}
		T.build(1,1,n);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(vis[i][j]||i==j)continue;
				ans+=1ll*(query(i,j)+1);
				vis[i][j]=vis[j][i]=1;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}