树的最大连通分支问题.cpp

王晓东算法设计与分析源码。vc下编译通过能够运行。且运行效率较高

#include<iostream>
using namespace std;
#define N 50005
struct node {
 int s;
 struct node *next;
};
typedef struct node *link;
link child[N];
int vis[N] = {0};
int sum[N]={0};
int w[N]={0};
int n;
int maxw = 0;
void init()
{
 int a,b;
 scanf("%d",&n);
 for(int i=1;i<=n;i++) scanf("%d",&w[i]);//cin >> w[i];
 for(int i=1;i<=n-1;i++){
  scanf("%d%d",&a,&b);//cin >> a >> b;
  link p = new node;
  p->s = a;
  p->next = child[b];
  child[b] = p;
  p = new node;
  p->s = b;
  p->next = child[a];
  child[a] = p;
 }
}
void build(int k)
{
 link p,q;
 vis[k] = 1;
 p = child[k];
 while(p){
  int i = p->s;
  if(vis[i])
   if(p==child[k]){
    child[k] = p->next;
    delete p;
    p = child[k];
   }
   else{
    q->next = p->next;
    delete p;
    p = q->next;
   }
   else{
    build(i);
    if(p==child[k]) q=child[k];
    else q = q->next;
    p = p->next;
   }
 }
}
void comp(int k)
{
 link p = child[k];
 while(p){
  int i = p->s;
  comp(i);
  if(sum[i]>0) sum[k]+=sum[i];
  p = p->next;
 }
 sum[k]+=w[k];
}
void out()
{
 for(int i=1;i<=n;i++)
  if(sum[i]>maxw)
   maxw = sum[i];
 printf("%d\n",maxw);//cout << maxw << endl;
}
int main()
{
 init();
 build(1);
 comp(1);
 out();
 //return 0;
 system("pause");
}