Codeforces Round #177 (Div. 1)
D:
求一棵树中有多少对不相交的路径，正着搞比较难，反着搞就简单多了，c(n,2)*c(n，2)减去非法的
对于每个子树，分为在子树内部相交 和 外部的点延伸到子树内部两类，都剪掉就好了
[cpp]
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
int a[80001];
vector<int> edge[80001];
long long ans;
int n;
void dfs(int u,int f)
{
a[u] = 1;
long long in = 0;
for(int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i];
if(v==f) continue;
dfs(v,u);
in += (long long)a[u]*a[v];
a[u]+=a[v];
}
ans -= in*(in+2*(long long)a[u]*(n-a[u]));
}
int main()
{
int a, b , i;
cin>>n;
for(i = 1; i < n; i++)
{
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
ans = (long long)n * (n-1) / 2;
ans *= ans;
dfs(1,0);
cout<<ans<<endl;
return 0;
}
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
int a[80001];
vector<int> edge[80001];
long long ans;
int n;
void dfs(int u,int f)
{
a[u] = 1;
long long in = 0;
for(int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i];
if(v==f) continue;
dfs(v,u);
in += (long long)a[u]*a[v];
a[u]+=a[v];
}
ans -= in*(in+2*(long long)a[u]*(n-a[u]));
}
int main()
{
int a, b , i;
cin>>n;
for(i = 1; i < n; i++)
{
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
ans = (long long)n * (n-1) / 2;
ans *= ans;
dfs(1,0);
cout<<ans<<endl;
return 0;
}
补充：软件开发 , C++ ,
