比较简单的树形DP
题意：一个公司有一个电话网络，每个人的电话只和他的直接上级或者直接下属相连通。整个电话的网络和人事上下级关系一样，是一个树形的结构。现在Tanya希望向网络内的所有人传递一个信息，他就需要去打电话，他每分钟只能打一个电话，且他只能给他的直接上级或下属打电话，问最少需要多少时间，可以使得整个网络都得到这一消息。
想法应该很简单，tanya对应的点当根节点，对所有节点来说，他对应的哪个儿子节点需要把消息发布到整棵子树的时间越长，就肯定应该给谁先打电话。然后对时间排序，稍作处理就不难得出答案。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 const int maxn = 100010; 7 vector<int> G[maxn]; 8 bool vis[maxn]; 9 10 int cmp(int a,int b){ 11 return a > b; 12 } 13 14 int dfs(int k){ 15 vis[k] = 1; 16 vector<int> tmp; 17 for(int i = 0;i < G[k].size();i++){ 18 int t = G[k][i]; 19 if(!vis[t]){ 20 int a = dfs(t); 21 tmp.push_back(a); 22 } 23 } 24 sort(tmp.begin(),tmp.end(),cmp); 25 int ans = 0; 26 for(int i = 0;i < tmp.size();i++){ 27 if(tmp[i]+i+1 > ans) 28 ans = tmp[i]+i+1; 29 } 30 //printf("dfs(%d) = %d\n",k,ans); 31 return ans; 32 } 33 34 int main(){ 35 int n; 36 while(scanf("%d",&n) != EOF){ 37 for(int i = 1;i <= n;i++) G[i].clear(); 38 for(int i = 1;i <= n;i++){ 39 int j; 40 while(scanf("%d",&j),j){ 41 G[i].push_back(j); 42 G[j].push_back(i); 43 } 44 } 45 int t; 46 scanf("%d",&t); 47 printf("%d\n",dfs(t)); 48 } 49 return 0; 50 }