树上选点蓝桥Java题解

树上选点是蓝桥杯Java题目中的一种类型，通常需要在给定的树结构中选择一个或多个节点作为目标节点，并进行相应的操作。下面是一个简单的树上选点蓝桥Java题解的示例：

题目描述：
给定一棵有N个节点的树，每个节点上都有一个非负整数值。现在需要选择一些节点，使得选择的节点的值之和最大，且所选节点不能相邻（即选了一个节点，则其父节点和子节点都不能选）。请编写一个程序，计算出最大的节点值之和。

解题思路：
这是一个典型的动态规划问题。我们可以定义一个数组dp，其中dp[i]表示以第i个节点为根节点的子树中所选节点的最大值之和。对于每个节点i，有两种情况：
1. 选择节点i：则其子节点都不能选，所以dp[i] = val[i] + dp[grandchild1] + dp[grandchild2] + ...
2. 不选择节点i：则其子节点可以选择或不选择，所以dp[i] = max(dp[child1], dp[child2], ...)

根据以上思路，我们可以使用递归或者迭代的方式来计算dp数组。最终，所求的最大值即为dp，其中1表示根节点。

代码示例：

public class TreeSelectPoint {
    public static void main(String[] args) {
        int[] values = {0, 1, 2, 3, 4, 5}; // 节点值数组，下标从1开始
        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}; // 树的边关系数组

        int n = values.length - 1; // 节点个数
        int[] dp = new int[n + 1]; // 动态规划数组

        // 构建树的邻接表
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adjacencyList.get(u).add(v);
            adjacencyList.get(v).add(u);
        }

        dfs(1, -1, values, adjacencyList, dp); // 从根节点开始进行深度优先搜索

        System.out.println(dp[1]); // 输出最大节点值之和
    }

    private static void dfs(int cur, int parent, int[] values, List<List<Integer>> adjacencyList, int[] dp) {
        dp[cur] = values[cur]; // 初始化当前节点的dp值为节点值

        for (int child : adjacencyList.get(cur)) {
            if (child != parent) { // 避免重复访问父节点
                dfs(child, cur, values, adjacencyList, dp);
                dp[cur] += dp[child]; // 更新当前节点的dp值
            }
        }
    }
}