这标题起的及容易被人忽略了
为了表述方便，我称“选出的点的权值和最大是多少”这个值为这棵树的最大值。用f(tree)来表示。
再设f0(tree)为树不包含根结点时的最大值，f1(tree)为树包含根结点时的最大值，v(node)为结点的权值，则
f0(tree) = sum(f(sub_tree))
f1(tree) = sum(f0(sub_tree)) + v(root)
f(tree) = max(f0(tree), f1(tree))
相比算法模型分析构造的难度，我倒觉得这题更有意义的地方在于如何构造这棵树。
下面是我的一个方案，时间复杂度O(N)，空间复杂度S(N)。楼主顺道提交一下给我看看结果
程序代码：
#include <stdio.h>
#define LEN 100000
struct child_list;
typedef struct
{
char f;
int v0, v1;
struct child_list * h;
}NODE;
typedef struct child_list
{
NODE * p;
struct child_list * next;
}CL;
NODE A[LEN];
CL C[(LEN - 1) * 2];
int cal(NODE * r)
{
NODE * np;
CL * cp;
r->f = 1;
for(cp = r->h; cp; cp = cp->next)
{
if((np = cp->p)->f) continue;
r->v0 += cal(np);
r->v1 += np->v0;
}
return r->v0 > r->v1 ? r->v0 : r->v1;
}
int main()
{
int an, cn = 0, i, j, k;
scanf("%d", &an);
for(i = 0; i < an; scanf("%d", &A[i++].v1));
for(i = 1; i < an; i++)
{
scanf("%d%d", &j, &k);
j--; k--;
C[cn].p = &A[j];
C[cn].next = A[k].h;
A[k].h = &C[cn++];
C[cn].p = &A[k];
C[cn].next = A[j].h;
A[j].h = &C[cn++];
}
printf("%d", cal(A));
return 0;
}
2014-03-09 21:28
