트리 dp 입문

 1 #include <algorithm>

 2 #include <iostream>

 3 #include <cstring>

 4 #include <cstdio>

 5 using namespace std;

 6 

 7 const int N = 1500;

 8 bool flag[N];

 9 int head[N];

10 int dp[N][2];

11 int e, n;

12 

13 void init()

14 {

15     e = 0;

16     memset( flag, true, sizeof(flag) );

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

18 }

19 

20 struct Edge

21 {

22     int v, next;

23 } edge[N];

24 

25 void addEdge( int u, int v )

26 {

27     edge[e].v = v;

28     edge[e].next = head[u];

29     head[u] = e++;

30 }

31 

32 void dfs( int u )

33 {

34     dp[u][0] = 0;

35     dp[u][1] = 1;

36     for ( int i = head[u]; i != -1; i = edge[i].next )

37     {

38         int v = edge[i].v;

39         dfs(v);

40         dp[u][0] += dp[v][1];

41         dp[u][1] += min( dp[v][0], dp[v][1] );

42     }

43 }

44 

45 int main ()

46 {

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

48     {

49         init();

50         for ( int i = 0; i < n; i++ )

51         {

52             int u, v, m;

53             scanf("%d:(%d)", &u, &m);

54             while ( m-- )

55             {

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

57                 addEdge( u, v );

58                 flag[v] = false;

59             }

60         }

61         int root;

62         for ( int i = 0; i < n; i++ )

63         {

64             if ( flag[i] )

65             {

66                 root = i;

67                 break;

68             }

69         }

70         dfs(root);

71         int ans = min( dp[root][0], dp[root][1] );

72         printf("%d
", ans);

73     }

74     return 0;

75 }