hdu4705 Y--树形dp

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=4705​​

题意：一棵树，求三个点不在一条线的个数。

分析：注意，反过来求，求出三个点在一条线的个数，最后总数减去在一条线的就行。注意，在一条线的意思也可能是三个点不是连续邻近，只要三个点能用一条线连起来就行，不管中间会隔多少点。

#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:16777216")
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

long long n;//注意是long long
long long ans;
bool vis[100005];
int son[100005];
vector<int> vec[100005];

void tree_dp(int u)
{
  son[u] = 1;
  vis[u] = 1;
  int t = 0;
  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i];
    if (!vis[v])
    {
      tree_dp(v);
      son[u] += son[v];//已经求出的儿子的个数,for结束才是求出所有儿子个数
      ans += long long((n - son[u])*son[v]);//n应该是long long，int类型最多10位
    }
  }
}

int main() 
{
  while (~scanf("%I64d", &n))
  {
    for (int i = 1; i <= n; i++)
    { 
      vis[i] = 0;
      vec[i].clear();
    }

    int u, v;
    for (int i = 1; i < n; i++) 
    {
      scanf("%d%d", &u, &v);
      vec[u].push_back(v);
      vec[v].push_back(u);
    }

    ans = 0;
    tree_dp(1);
    long long t = n*(n - 1)*(n - 2) / 6;
    printf("%I64d\n", t - ans);
  }
  return 0;
}