C++14(g++5.4) 解法, 执行用时: 99ms, 内存消耗: 11008K, 提交时间: 2020-03-22 10:59:52

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,ans[N],cnt;
vector<int>g[N];
ll dfs(int u,int fa){
	ll sz=1;
	for(auto v:g[u])
		if(v!=fa) sz+=dfs(v,u);
	ans[cnt++]=sz*(n-sz);
	return sz;
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	sort(ans,ans+cnt);
	ll res=0;
	for(int i=n-1;i>0;i--)
		 res+=ans[n-i]*i;
		cout<<res<<endl;
	return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 94ms, 内存消耗: 10988K, 提交时间: 2020-03-22 14:31:28

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,ans[N],cnt;
vector<int>g[N];
ll dfs(int u,int fa)
{
	ll sz=1;
	for(auto v:g[u])
	if(v!=fa) sz+=dfs(v,u);
	ans[cnt++]=sz*(n-sz);
	return sz;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	sort(ans,ans+cnt);
	ll res=0;
	for(int i=n-1;i>0;i--)
	res+=ans[n-i]*i;
	cout<<res<<endl;
	return 0;
}