Codeforces Round #177 (Div. 1)
这场略水，不然我是来不及打开第四题的，不过最后也没做出来。。。。。
小小的涨了108分
D:
求一棵树中有多少对不相交的路径，正着搞比较难，反着搞就简单多了，c(n,2)*c(n，2)减去非法的
对于每个子树，分为在子树内部相交 和 外部的点延伸到子树内部两类，都剪掉就好了
#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;}