2016 Multi-University Training Contest 1

题目：https://cn.vjudge.net/contest/296683

A - Abandoned country

HDU - 5723 求最小生成树，再求这个最小生成树上任意两个点的最短距离期望 任意两个点情况数就是C(n,2)，任意两个点的距离和可以转化为求每条边的贡献和 而每条边的贡献就是u->v valsz[v](n-sz[v]用dp[u]储存所有和u相连的边的贡献和，简单树形Dp

#include
using namespace std;
#define ll long long
const int maxn=100010;
const int maxm=1000010;

struct edge{
	int u,v,w,nxt;
}e[maxm];
int head[maxn],tot;
int n,m;
int f[maxn];


void init()
{
	memset(head,-1,sizeof(head));
	tot=0;
}

void addedge(int u,int v,int w)
{
	e[tot].u=u;
	e[tot].v=v;
	e[tot].w=w;e[tot].nxt=head[u];
	head[u]=tot++;
}
int find1(int x)
{
	return x==f[x]?x:f[x]=find1(f[x]);
}
bool union1(int a,int b)
{
	int fa=find1(a),fb=find1(b);
	if(fa!=fb){
		f[fa]=fb;
		return false;
	}
	return true;
}

struct node{
	int a,b,c;
}hh[maxm];
bool cmp(const node& a,const node& b)
{
	return a.c