节点选择（树形动态规划）_树上选点

问题描述

有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
输入格式

第一行包含一个整数 n 。

接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行，每行描述树上的一条边。
输出格式
输出一个整数，代表选出的点的权值和的最大值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
12
样例说明
选择3、4、5号点，权值和为 3+4+5 = 12 。
数据规模与约定

对于20%的数据， n <= 20。

对于50%的数据， n <= 1000。

对于100%的数据， n <= 100000。

权值均为不超过1000的正整数。

求解
解决本题的思路是：
采用扩散深搜的方法，现将所有节点遍历一遍，然后回溯，依次记录每个节点取或者不取的权值之和（包括其子节点），如：取i点，则加上不取该子字节的权值之和； 若不取i点，则比较取或者不取该子节点的权值和的最大值，取大者相加。一直回溯到根节点，最后再比较一下取还是不取根节点，并显示最终结果。

代码如下：

import java.util.Arrays;
import java.util.Scanner;

/** 
 * @author 作者 : Cactus
 * @version 创建时间：2018-3-20 下午09:23:20 
 */
public class Main {
	private static int[][] arr_node = new int[100000][2];// 用于记录每个节点，选1或者不选0，其权值和（该节点和其所有子节点）
	private static int[][] arr_route = new int[100000][100];// 用于记录每个节点的孩子节点
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//Arrays.fill(arr_node, 0);
		for(int i = 1; i <= n; i++){
			arr_node[i][1] = sc.nextInt();
		}
		//Arrays.fill(arr_route, 0);
		int start,end,j,k;
		for(int i = 0; i < n - 1; i++){
			start = sc.nextInt();
			end = sc.nextInt();
			j = 0;
			k = 0;
			while(arr_route[start][j] != 0){
				j++;
			}
			arr_route[start][j] = end;
			while(arr_route[end][k] != 0){
				k++;
			}
			arr_route[end][k] = start;
			
		}
		sc.close();
		//以上为存放相关数据
		dfs(1,0); //动态规划+深度搜索，从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
		System.out.println(fmax(arr_node[1][0],arr_node[1][1])); //比较第一个节点，选或不选哪个权值和更大，并输出
	}
	private static void dfs(int x, int f){
		int i,k;
		k = 0;
		while((i = arr_route[x][k]) != 0){ 
			k++;
			if(i != f){   //当前节点！=其父节点，防止出现start的孩子成为start的父亲情况
				dfs(i,x); //深搜
				arr_node[x][1] += arr_node[i][0]; //取x,则加上不取其子节点i的权值和
				arr_node[x][0] += fmax(arr_node[i][0],arr_node[i][1]);// 不取x,则选择取或不取其子节点i的权值和大者
				//状态转移方程
			}
		}
	}
	private static int fmax(int a, int b){
		return a > b ? a : b;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

最终的测试结果只得了50分，剩下的五个测试用例，提示运行错误，目前还没有找到原因（有可能是超时）。 但是C++版的完全是可以运行通过的。

这个代码后续再改进吧，最近要加快刷题速度，只能先放一放了。
近期涉及到很多算法题，做起来很吃力，也从侧面提醒了自己基础不够扎实的缺陷，不过也很开心，虽然做的吃力，但是能够明显感觉到自己的进步。加油！