Farmer John has a list of N (3 <= N <= 10,000) chores that must be completed. Each chore requires an integer time (1 <= length of time <= 100) to complete and there may be other chores that must be completed before this chore is started. We will call these prerequisite chores. At least one chore has no prerequisite: the very first one, number 1. Farmer John's list of chores is nicely ordered, and chore K (K > 1) can have only chores 1,.K-1 as prerequisites. Write a program that reads a list of chores from 1 to N with associated times and all perquisite chores. Now calculate the shortest time it will take to complete all N chores. Of course, chores that do not depend on each other can be performed simultaneously.

* Lines 2..N+1: N lines, each with several space-separated integers. Line 2 contains chore 1; line 3 contains chore 2, and so on. Each line contains the length of time to complete the chore, the number of the prerequisites, Pi, (0 <= Pi <= 100), and the Pi prerequisites (range 1..N, of course).

[Here is one task schedule:


        Chore 1 starts at time 0, ends at time 5.


        Chore 2 starts at time 5, ends at time 6.


        Chore 3 starts at time 6, ends at time 9.


        Chore 4 starts at time 5, ends at time 11.


        Chore 5 starts at time 11, ends at time 12.


        Chore 6 starts at time 11, ends at time 19.


        Chore 7 starts at time 19, ends at time 23.


]
題解：樹形DP入門題。從根節點往下依次更新出每一個節點的最短時間，則該最短時間的最大值即為：完成家務的最短時間。
參考代碼為：

#include <iostream>

#include <cstring>

using namespace std;

const int maxn=10005;

int c[maxn],n[maxn],dp[maxn];

int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);

   	int N,temp,sum=-maxn;

   	memset(dp,0,sizeof dp);

   	cin>>N;

   	for(int i=1;i<=N;i++)

   {

    	cin>>c[i]>>n[i];

    	if(i==1) dp[i]=c[i];

    	else

		{

       	 	int max=-maxn;

        	if(n[i]==0) dp[i]=c[i];

        	else

			{

            	for(int j=0;j<n[i];j++)

				{

                	cin>>temp;

                	if(dp[temp]>max) max=dp[temp];

            	}

            	dp[i]=max+c[i];

        	}

    	}

      	if(dp[i]>sum) sum=dp[i];

   	}

   	cout<<sum<<endl;

    return 0;

}

/*

7

5 0

1 1 1

3 1 2

6 1 1

1 2 2 4

8 2 2 4

4 3 3 5 6

*/