题目描述

经过了几周的辛苦工作,贝茜终于迎来了一个假期.作为奶牛群中最会社交的牛,她希望去拜访N(1<=N<=50000)个朋友.这些朋友被标号为1..N.这些奶牛有一个不同寻常的交通系统,里面有N-1条路,每条路连接了一对编号为C1和C2的奶牛(1 <= C1 <= N; 1 <= C2 <= N; C1<>C2).这样,在每一对奶牛之间都有一条唯一的通路. FJ希望贝茜尽快的回到农场.于是,他就指示贝茜,如果对于一条路直接相连的两个奶牛,贝茜只能拜访其中的一个.当然,贝茜希望她的假期越长越好,所以她想知道她可以拜访的奶牛的最大数目.

输入

第1行:单独的一个整数N

第2..N行:每一行两个整数,代表了一条路的C1和C2.

输出

单独的一个整数,代表了贝茜可以拜访的奶牛的最大数目.

样例输入

7

6 2

3 4

2 3

1 2

7 6

5 6

样例输出

4

---

题解

裸的树形dp。

f[x]代表拜访x时最大数量，g[x]代表不拜访x时最大数量。

那么易推得f[x]=1+∑g[to[i]]，g[x]=∑max(f[to[i]],g[to[i]])。

答案即为max(f[1],g[1])。

#include 
     
      #include 
      
       int to[100001] , next[100001] , head[50001] , f[50001] , g[50001] , cnt;int max(int a , int b){    return a > b ? a : b;}void add(int x , int y){    to[cnt] = y;    next[cnt] = head[x];    head[x] = cnt ++ ;}void dp(int x , int last){    int i , y;    f[x] = 1;    for(i = head[x] ; i != -1 ; i = next[i])    {        y = to[i];        if(y == last)            continue;        dp(y , x);        f[x] += g[y];        g[x] += max(f[y] , g[y]);    }}int main(){    int n , i , x , y;    scanf("%d" , &n);    memset(head , -1 , sizeof(head));    for(i = 1 ; i <= n - 1 ; i ++ )    {        scanf("%d%d" , &x , &y);        add(x , y);        add(y , x);    }    dp(1 , 0);    printf("%d\n" , max(f[1] , g[1]));    return 0;}