contree.cpp

给定一棵树T

#include "iostream.h"
#include <fstream>
using namespace std;
struct Cnode   //用结构体来表示结点
{
	long weight;   //结点的权值
	int father;    //结点的父亲结点
	int childnum;  //结点的儿子个数
	long wMax;     //结点的最大连通分支权值
	bool visited;  //该结点是否被访问过
};
int main()
{
    ifstream fin("input.txt");
	ofstream fout("output.txt");
	int i;
	long n,u,v;	
	fin>>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;
		fin>>(tree[i].weight);
		tree[i].wMax=tree[i].weight;
	}		
	for (i=1;i<=(n-1);i++)//输入数据
	{
		fin>>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;
	fout<<max;
	delete [] tree;
	return 0;
}