#include<iostream>
#include<string>
#define max(x,y) (x>y?x:y)
using namespace std;
int vis[6010],dp[6010][2],n,father[6010];
void dfs(int node)
{
 int i;
 vis[node]=1;
 for(i=1;i<=n;i++)
  if(!vis[i] && father[i]==node && father[i]!=i)//用father[i]!=i判断不是树的根
  {
   dfs(i);
   dp[node][0]+=max(dp[i][1],dp[i][0]);
   dp[node][1]+=dp[i][0];
  }
}
int main()
{
 int i;
 while(cin>>n)
 {
  memset(dp,0,sizeof(dp));
  for(i=1;i<=n;i++)
   cin>>dp[i][1];
  int temp1,temp2,root=0;
  for(i=1;i<=n;i++)
   father[i]=i;
  //memset(father,0,sizeof(father));
  while(cin>>temp1>>temp2,temp1+temp2>0)
  {
   father[temp1]=temp2;
   if(root==temp1 || root==0)
    root=temp2;
  }
  
  memset(vis,0,sizeof(vis));
  dfs(root);
  int max1=max(dp[root][1],dp[root][0]);
  cout<<max1<<endl;
 }
 return 0;
}

• Re:用father[i]!=i判断不是树的根，为什么这样不行，求教 (24) 150137 2016-06-12 18:55:07