树上求和(dfs)
按照题目中的要求，只要统计每条边出现的次数，然后队次数排序，最后以后×n-1,n-2...1就行。
如何统计每个边出现的次数？（dfs）
比如边1，左边有两个顶点，右边有两个顶点。因此共包含边1 四次（2*2）。
1-2-3，1-2-3-4，2-3，2-3-4，四次，
所以我们只要统计每个边的左侧和右侧有多少顶点就可以。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
vector<int> g[maxn];
ll res[maxn],ans=0;
bool visit[maxn];
int n,x,y;//输入
void init(int n){
for(int i=0;i<=n;i++){
res[i]=0;
visit[i]=false;
}
}int cnt=0;
ll dfs(int s){
visit[s]=true;
ll num=1;
for(int i=0;i<g[s].size();i++){
if(!visit[g[s][i]]){
num+=dfs(g[s][i]);//求每个点的左边顶点数
}
}
if(s!=1){
res[++cnt]=num*(n-num); //n-num为每个边的右边顶点数
}
return num;
}
int main(){
cin>>n;
init(n);
for(int i=0;i<n-1;i++){
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
sort(res+1,res+1+cnt);
for(int i=1;i<n;i++){
ans+=res[i]*(n-i);
}cout<<ans<<endl;
return 0;
} 
查看10道真题和解析