# 树的最大连通分支问题

``````5
-1 1 3 1 -1
4 1
1 3
1 2
4 5
``````

``````4
``````

``````#include<iostream>
#include <fstream>
using namespace std;
struct Cnode
{
long weight;
int father;
int childnum;
long wMax;
bool visited;
};
int main()
{
int i;
long n,u,v;
cin>>n;
Cnode *tree=new Cnode[n+1];
for (i=1;i<=n;i++)
{
tree[i].father=0;
tree[i].childnum=0;
tree[i].visited=false;
cin>>(tree[i].weight);
tree[i].wMax=tree[i].weight;
}
for (i=1;i<=(n-1);i++)
{
cin>>u>>v;
tree[v].father=u;
tree[u].childnum++;
}
int root;
for (i=1;i<=n;i++)
if (tree[i].father==0)
root=i;
while (tree[root].childnum>0)
{
for (i=1;i<=n;i++)
if ((tree[i].childnum==0)&&(!tree[i].visited))
{
tree[i].visited=1;
tree[tree[i].father].childnum--;
if (tree[i].wMax>0)
tree[tree[i].father].wMax=tree[tree[i].father].wMax+tree[i].wMax;
}
}
long max=tree[1].wMax;
for (i=2;i<=n;i++)
if (tree[i].wMax>max)
max=tree[i].wMax;
cout<<max;
delete [] tree;
return 0;
}
``````

``````#include<iostream>
#include <fstream>
using namespace std;
struct Cnode
{
long weight;
int father;
int childnum;
long wMax;
bool visited;
};
int main()
{
int i;
long n,u,v;
cin>>n;
Cnode *tree=new Cnode[n+1];
for (i=1;i<=n;i++)
{
tree[i].father=0;
tree[i].childnum=0;
tree[i].visited=false;
cin>>(tree[i].weight);
tree[i].wMax=tree[i].weight;
}
for (i=1;i<=(n-1);i++)
{
cin>>u>>v;
tree[v].father=u;
tree[u].childnum++;
}
int root;
for (i=1;i<=n;i++)
if (tree[i].father==0)
root=i;
while (tree[root].childnum>0)
{
for (i=1;i<=n;i++)
if ((tree[i].childnum==0)&&(!tree[i].visited))
{
tree[i].visited=1;
tree[tree[i].father].childnum--;
if (tree[i].wMax>0)
tree[tree[i].father].wMax=tree[tree[i].father].wMax+tree[i].wMax;
}
}
long max=tree[1].wMax;
for (i=2;i<=n;i++)
if (tree[i].wMax>max)
max=tree[i].wMax;
cout<<max;
delete [] tree;
return 0;
}
``````