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;
}