HDu 4705ツリーdp

标题:木の上の任意の3つの点が1つの経路になく、このような3つの点の集合が何種類あるかを統計する.
3点構成のパス数S=C(n,3)=n*(n-1)*(n-2)/6
Sで3つの点を1つの経路上の数を減らすのが答えです.
中間点を2番目の点として列挙し、そのK本目の木の上で1番目の点を探して、残りの列挙されていないノードの中で、3番目の点として1つの点を探します.数を掛ける.
これにより問題は統計ノードのサブノード問題となり,簡単なツリーdpとなる.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#pragma comment(linker,"/STACk:102400000,102400000")
using namespace std;
vector<int> tree[100005];
typedef long long ll;
ll ans,ll n;
ll dfs(int k,int fa=-1)
{
    ll sum=0,son=0;
    for(int i=0;i<tree[k].size();i++)
        if(tree[k][i]!=fa){
            sum+=son=dfs(tree[k][i],k);
            ans+=son*(n-sum-1);
        }
    return sum+1;
}
int main()
{
    int a,b;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++) tree[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        ans=0;
        dfs(1);
        cout<<n*(n-1)*(n-2)/6-ans<<endl;
    }
    return 0;
}