hdu4705Y

链接

这题可以算树形DP吧 树上的递推

对于树上的某个节点 反着算比较好做 就是算有多少有simple路径的

固定某个节点u 另两个节点 有两种取法

1.从不同子树里各选一个

2.从所有子树里选一个 再从以u为跟的子树 外面选一个

求总和

 #pragma comment(linker, "/STACK:16777216")

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define N 100010

 #define LL __int64

 struct node

 {

     int u,v,next;

 }ed[N<<];

 int head[N],t;

 LL sum[N],ans,n;

 void init()

 {

     t = ;

     memset(head,-,sizeof(head));

 }

 void add(int u,int v)

 {

     ed[t].u = u;

     ed[t].v = v;

     ed[t].next = head[u];

     head[u] = t++;

 }

 LL dfs(int pre,int u)

 {

     int i;

     LL s=,ss;

     sum[u] = ;

     for(i = head[u]; i!=- ; i = ed[i].next)

     {

         int v = ed[i].v;

         if(v==pre) continue;

         ss = dfs(u,v);

         ans+=s*ss;

         s+=ss;

         sum[u]+=ss;

     }

     ans+=s*(n-sum[u]);

     return sum[u];

 }

 int main()

 {

     int i,u,v;

     while(scanf("%I64d",&n)!=EOF)

     {

         init();ans=;

         memset(sum,,sizeof(sum));

         for(i =  ; i < n ; i++)

         {

             scanf("%d%d",&u,&v);

             add(u,v);

             add(v,u);

         }

         dfs(-,);

         LL oo = (n-)*n/*(n-)/;

         printf("%I64d\n",oo-ans);

     }

     return ;

 }