一棵树,树的每条边有边权,现准备选择一些边染成红色, 要求不存在两条染红的边共用同一个点,且最终染红边的权值之和尽可能大。注:所谓树,即不包含重边、自环和回路的无向连通图。java代码实现
时间: 2024-05-02 20:21:43 浏览: 16
以下是Java代码实现:
```
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int n;
static int[] w;
static List<Integer>[] g;
static int[][] f;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
w = new int[n + 1];
g = new List[n + 1];
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
g[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
int u = in.nextInt();
int v = in.nextInt();
g[u].add(v);
g[v].add(u);
}
f = new int[n + 1][2];
dfs(1, 0);
System.out.println(Math.max(f[1][0], f[1][1]));
}
static void dfs(int u, int fa) {
f[u][0] = 0;
f[u][1] = w[u];
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
f[u][0] += Math.max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
}
}
```
算法思路:
使用动态规划来解决此问题。设 $f_{u,0/1}$ 表示以节点 $u$ 为根的子树中,不选/选节点 $u$ 的最大权值和。转移方程如下:
$$ f_{u,0} = \sum_{v \in son(u)} \max\{f_{v,0}, f_{v,1}\} $$
$$ f_{u,1} = w_u + \sum_{v \in son(u)} f_{v,0} $$
其中 $son(u)$ 表示节点 $u$ 的子节点集合。
最终答案即为 $\max\{f_{1,0}, f_{1,1}\}$,因为根节点 $1$ 可以选择不选或选。
时间复杂度:$O(n)$。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)