树上计数-hdu-4705-Y

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4705

题目大意：

给一棵树，求三点不能通过简单路径到达的种数（也就是不在一条线上）。

解题思路：

如果枚举Y形的话，要先枚举一个点，然后在子树中找三个点,这样找有点麻烦，复杂度应该为o(n^2)。如果求补集，找三点在一条线的情况就好找了，枚举中间的那个点还剩下两个点，直接o(n)就可以解决（每次计算当前子树到和前面子树）。

PS:树上计数：递归+dp+数学。一般都能很好解决。

遍历树只用记录父亲节点判有没访问即可。

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64

#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;


//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
//转化成补集，把四个点的问题转化成三个点，再在三个点中枚举中间点
//树的计数问题以后要多做了，大部分与递归和dp和数学有关
ll ans;

#define Maxn 110000
struct Edge   //无向边相当于有两条边
{
    int v;
    struct Edge * next;
}*head[Maxn<<1],edge[Maxn<<1];

int n,num;

void add(int a,int b)
{
    ++num;
    edge[num].v=b;
    edge[num].next=head[a],head[a]=&edge[num];
}

ll cnt[Maxn];

void dfs(int pre,int cur)
{
    struct Edge * p=head[cur];
    ll sum=0; //sum记录该节点的所有子树总结点数
    cnt[cur]=1; //表示以该节点为树根的所有节点总数
    while(p)
    {
      if(p->v==pre)
      {
         p=p->next;
         continue;
      }
      dfs(cur,p->v);//先把子树计算好 递归很强大，顺序导致用法很灵活
      ans-=sum*cnt[p->v]; //当前子树和前面所有子树的节点，两棵树各选一个节点
      sum+=cnt[p->v];
      cnt[cur]+=cnt[p->v];//统计
      p=p->next;
    }
    ans-=sum*(n-cnt[cur]); //在子树中选一点 然后在非子树中选一点，和cur点
}
int main()
{
   //freopen("01.in","r",stdin);
   //freopen("ans.out","w",stdout);
    int a,b;
    while(~scanf("%d",&n))
    {
        memset(head,NULL,sizeof(head));
        num=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        ans=(ll)n*(n-1)*(n-2)/6;//求补
        dfs(-1,1);
        printf("%I64d
",ans);
    }
   return 0;
}