登录最大节点价值之和
方法一：贪心
思路与算法
题目允许我们任意次选择树上任意一条边，将边上两点的值异或上 $k$，求所有节点值之和的最大值。
首先，由异或运算的性质可知，一个值 $a$ 异或奇数次另一个值 $k$，值为 $a \oplus k$，异或偶数次 $k$ 值为 $a$。其次，对于树上任意两点，存在一条路径，对路径上的每一条边进行操作，除了路径的起点和终点进行了一次异或，剩下的所有点都进行了两次异或，值不变。也就是等价于我们可以对树上任意两点进行一次异或操作。因此，问题转化为对树上任意两点进行异或 $k$ 操作，使得所有节点值之和最大。
我们可以使用贪心的思路来解决这个问题。令 $\textit{res}= \sum\limits_{i=0}^{n-1}\textit{nums}[i]$，$\textit{diff}[i] = (\textit{nums}[i]\oplus k) - \textit{nums}[i]$，并将 $\textit{diff}$ 数组排序，按从大到小的顺序遍历 $\textit{diff}$。每次将 $\textit{diff}$ 的两个元素相加，如果它们的和非负，则把和加到 $\textit{res}$；如果和为负数，则结束遍历。遍历完成后的 $\textit{res}$ 即为和的最大值。
将 $\textit{diff}$ 排序，从大到小遍历，每次取两个值相加的操作，表示每次取两个异或后值增加最多的点进行操作，从而使节点值的总和增加最多。由于没有其它操作能使总和更大，贪心策略是正确的。
代码
###C++
class Solution {
public:
long long maximumValueSum(vector<int>& nums, int k,
vector<vector<int>>& edges) {
long long res = accumulate(nums.begin(), nums.end(), 0ll);
vector<int> diff;
for (auto& a : nums) {
diff.push_back((a ^ k) - a);
}
sort(diff.begin(), diff.end());
for (int i = diff.size() - 1; i > 0 && diff[i] + diff[i - 1] >= 0;
i -= 2) {
res += max(0, diff[i] + diff[i - 1]);
}
return res;
}
};
###Java
class Solution {
public long maximumValueSum(int[] nums, int k, int[][] edges) {
long res = 0;
int[] diff = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
res += nums[i];
diff[i] = (nums[i] ^ k) - nums[i];
}
Arrays.sort(diff);
for (int i = diff.length - 1; i > 0 && diff[i] + diff[i - 1] >= 0; i -= 2) {
res += diff[i] + diff[i - 1];
}
return res;
}
}
###Python
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
res = sum(nums)
diff = [(x ^ k) - x for x in nums]
diff.sort()
i = len(diff) - 1
while i > 0 and diff[i] + diff[i - 1] >= 0:
res += diff[i] + diff[i - 1]
i -= 2
return res
###C
int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); }
long long maximumValueSum(int* nums, int numsSize, int k, int** edges,
int edgesSize, int* edgesColSize) {
long long res = 0;
int diff[numsSize];
for (int i = 0; i < numsSize; ++i) {
res += nums[i];
diff[i] = (nums[i] ^ k) - nums[i];
}
qsort(diff, numsSize, sizeof(int), cmp);
for (int i = numsSize - 1; i > 0 && diff[i] + diff[i - 1] >= 0; i -= 2) {
res += diff[i] + diff[i - 1];
}
return res;
}
###Golang
func maximumValueSum(nums []int, k int, edges [][]int) int64 {
res := int64(0)
diff := make([]int, len(nums))
for i, x := range nums {
res += int64(x)
diff[i] = (x ^ k) - x
}
sort.Ints(diff)
for i := len(diff) - 1; i > 0 && diff[i]+diff[i-1] >= 0; i -= 2 {
res += int64(diff[i] + diff[i-1])
}
return res
}
###C#
public class Solution {
public long MaximumValueSum(int[] nums, int k, int[][] edges) {
long res = nums.Sum(x => (long)x);
List<int> diff = nums.Select(x => (x ^ k) - x).ToList();
diff.Sort();
for (int i = diff.Count - 1; i > 0 && diff[i] + diff[i - 1] >= 0; i -= 2) {
res += diff[i] + diff[i - 1];
}
return res;
}
}
###Rust
impl Solution {
pub fn maximum_value_sum(nums: Vec<i32>, k: i32, edges: Vec<Vec<i32>>) -> i64 {
let mut res: i64 = nums.iter().map(|&x| x as i64).sum();
let mut diff: Vec<i32> = nums.iter().map(|&x| (x ^ k) - x).collect();
diff.sort();
let mut i = diff.len();
while i >= 2 && diff[i - 1] + diff[i - 2] >= 0 {
res += (diff[i - 1] + diff[i - 2]) as i64;
i -= 2;
}
res
}
}
###JavaScript
var maximumValueSum = function(nums, k, edges) {
let res = nums.reduce((a, b) => a + b, 0);
let diff = nums.map(x => (x ^ k) - x);
diff.sort((a, b) => a - b);
for (let i = diff.length - 1; i > 0 && diff[i] + diff[i - 1] >= 0; i -= 2) {
res += diff[i] + diff[i - 1];
}
return res;
};
###TypeScript
function maximumValueSum(nums: number[], k: number, edges: number[][]): number {
let res = nums.reduce((a, b) => a + b, 0);
let diff = nums.map(x => (x ^ k) - x);
diff.sort((a, b) => a - b);
for (let i = diff.length - 1; i > 0 && diff[i] + diff[i - 1] >= 0; i -= 2) {
res += diff[i] + diff[i - 1];
}
return res;
};
复杂度分析
- 时间复杂度：$O(n\log n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。对与 $\textit{nums}$ 长度相同的数组 $\textit{diff}$ 排序需要 $O(n\log n)$ 的时间，遍历需要 $O(n)$，因此总的时间复杂度为 $O(n\log n)$。
- 空间复杂度：$O(n)$。需要存储与 $\textit{nums}$ 长度相同的数组 $\textit{diff}$。
方法二：树形动态规划
思路与算法
令 $f[u][0]$ 表示以 $u$ 为根的子树，$u$ 没有异或上 $k$ 时的最大和，$f[u][1]$ 表示以 $u$ 为根的子树，$u$ 被异或上 $k$ 时的最大和。枚举 $u$ 的子节点 $v$，考虑是否操作这两个点。
令 $r_0=\max(f[v][0]+\textit{nums}[v],f[v][1]+(\textit{nums}[v]\oplus k))$，即不操作 $u$ 和 $v$ 时子树 $v$ 的最大和，$r_1=\max(f[v][1]+\textit{nums}[v],f[v][0]+(\textit{nums}[v]\oplus k))$，即操作 $u$ 和 $v$ 时子树 $v$ 的最大和，则有转移方程：
$$
\begin{aligned}
f[u][0] &= \max(f[u][0]+r_0,f[u][1]+r_1) \
f[u][1] &= \max(f[u][1]+r_0,f[u][0]+r_1)
\end{aligned}
$$
初始值 $f[u][0]=0,f[u][1]=-\infty$。由于一开始没有操作，$u$ 不可能被操作，因此 $f[u][1]=-\infty$。结果为 $f[n][0]$。
代码
###C++
class Solution {
public:
long long maximumValueSum(vector<int> &nums, int k, vector<vector<int>> &edges) {
int n = nums.size();
vector<vector<int>> g(n);
for (auto &e : edges) {
int u = e[0], v = e[1];
g[u].push_back(v);
g[v].push_back(u);
}
function<pair<long long, long long>(int, int)> dfs = [&](int u, int fa) -> pair<long long, long long> {
long long f0 = 0, f1 = LLONG_MIN;
for (auto &v : g[u]) {
if (v != fa) {
auto [r0, r1] = dfs(v, u);
long long t = max(f1 + r0, f0 + r1);
f0 = max(f0 + r0, f1 + r1);
f1 = t;
}
}
return {max(f0 + nums[u], f1 + (nums[u] ^ k)), max(f1 + nums[u], f0 + (nums[u] ^ k))};
};
return dfs(0, -1).first;
}
};
###Java
class Solution {
public long maximumValueSum(int[] nums, int k, int[][] edges) {
int n = nums.length;
List<Integer>[] g = new ArrayList[n];
Arrays.setAll(g, i -> new ArrayList<>());
for (int[] e : edges) {
int u = e[0], v = e[1];
g[u].add(v);
g[v].add(u);
}
return dfs(0, -1, g, nums, k)[0];
}
private long[] dfs(int u, int fa, List<Integer>[] g, int[] nums, int k) {
long f0 = 0, f1 = Long.MIN_VALUE;
for (int v : g[u]) {
if (v != fa) {
long[] res = dfs(v, u, g, nums, k);
long r0 = res[0], r1 = res[1];
long t = Math.max(f1 + r0, f0 + r1);
f0 = Math.max(f0 + r0, f1 + r1);
f1 = t;
}
}
long x = nums[u], y = nums[u] ^ k;
return new long[] {
Math.max(f0 + x, f1 + y),
Math.max(f1 + x, f0 + y)
};
}
}
###Python
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
def dfs(u: int, fa: int) -> Tuple[int, int]:
f0, f1 = 0, -inf
for v in g[u]:
if v != fa:
r0, r1 = dfs(v, u)
t = max(f1 + r0, f0 + r1)
f0 = max(f0 + r0, f1 + r1)
f1 = t
return (
max(f0 + nums[u], f1 + (nums[u] ^ k)),
max(f1 + nums[u], f0 + (nums[u] ^ k)),
)
return dfs(0, -1)[0]
###C
int head[100010], to[100010 << 1], nxt[100010 << 1], tot = 0;
void add_edge(int u, int v) {
to[tot] = v;
nxt[tot] = head[u];
head[u] = tot++;
}
long long max(long long a, long long b) { return a > b ? a : b; }
void dfs(int u, int parent, int* nums, int k, long long* f0,
long long* f1) {
long long t0 = 0, t1 = LLONG_MIN;
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
if (v != parent) {
long long r0, r1;
dfs(v, u, nums, k, &r0, &r1);
long long t = max(t1 + r0, t0 + r1);
t0 = max(t0 + r0, t1 + r1);
t1 = t;
}
}
long long x = nums[u], y = nums[u] ^ k;
*f0 = max(t0 + x, t1 + y);
*f1 = max(t1 + x, t0 + y);
}
long long maximumValueSum(int* nums, int numsSize, int k, int** edges,
int edgesSize, int* edgesColSize) {
for (int i = 0; i < numsSize; ++i)
head[i] = -1;
tot = 0;
for (int i = 0; i < edgesSize; ++i) {
int u = edges[i][0], v = edges[i][1];
add_edge(u, v);
add_edge(v, u);
}
long long f0, f1;
dfs(0, -1, nums, k, &f0, &f1);
return f0;
}
###Golang
func maximumValueSum(nums []int, k int, edges [][]int) int64 {
n := len(nums)
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
var dfs func(u, fa int) (int64, int64)
dfs = func(u, fa int) (int64, int64) {
f0, f1 := int64(0), int64(-1<<63)
for _, v := range g[u] {
if v != fa {
r0, r1 := dfs(v, u)
t := max(f1+r0, f0+r1)
f0 = max(f0+r0, f1+r1)
f1 = t
}
}
x := int64(nums[u])
y := int64(nums[u] ^ k)
return max(f0+x, f1+y), max(f1+x, f0+y)
}
ans, _ := dfs(0, -1)
return ans
}
###C#
public class Solution {
public long MaximumValueSum(int[] nums, int k, IList<IList<int>> edges) {
int n = nums.Length;
List<int>[] g = new List<int>[n];
for (int i = 0; i < n; i++) {
g[i] = new List<int>();
}
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
g[u].Add(v);
g[v].Add(u);
}
(long f0, long f1) Dfs(int u, int fa) {
long f0 = 0, f1 = long.MinValue;
foreach (int v in g[u]) {
if (v != fa) {
var (r0, r1) = Dfs(v, u);
long t = Math.Max(f1 + r0, f0 + r1);
f0 = Math.Max(f0 + r0, f1 + r1);
f1 = t;
}
}
long x = nums[u], y = nums[u] ^ k;
return (Math.Max(f0 + x, f1 + y), Math.Max(f1 + x, f0 + y));
}
return Dfs(0, -1).f0;
}
}
###Rust
impl Solution {
pub fn maximum_value_sum(nums: Vec<i32>, k: i32, edges: Vec<Vec<i32>>) -> i64 {
let n = nums.len();
let mut g = vec![vec![]; n];
for e in edges {
let (u, v) = (e[0] as usize, e[1] as usize);
g[u].push(v);
g[v].push(u);
}
fn dfs(u: usize, fa: usize, g: &Vec<Vec<usize>>, nums: &Vec<i32>, k: i32) -> (i64, i64) {
let mut f0 = 0i64;
let mut f1 = i64::MIN;
for &v in &g[u] {
if v != fa {
let (r0, r1) = dfs(v, u, g, nums, k);
let t = (f1 + r0).max(f0 + r1);
f0 = (f0 + r0).max(f1 + r1);
f1 = t
}
}
let x = nums[u] as i64;
let y = (nums[u] ^ k) as i64;
(
(f0 + x).max(f1 + y),
(f1 + x).max(f0 + y),
)
}
dfs(0, n, &g, &nums, k).0
}
}
###JavaScript
var maximumValueSum = function (nums, k, edges) {
const n = nums.length;
const g = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const dfs = (u, fa) => {
let f0 = 0, f1 = -Infinity;
for (const v of g[u]) {
if (v !== fa) {
const [r0, r1] = dfs(v, u);
let t = Math.max(f1 + r0, f0 + r1);
f0 = Math.max(f0 + r0, f1 + r1);
f1 = t;
}
}
const x = nums[u], y = nums[u] ^ k;
return [Math.max(f0 + x, f1 + y), Math.max(f1 + x, f0 + y)];
};
return dfs(0, -1)[0];
};
###TypeScript
function maximumValueSum(nums: number[], k: number, edges: number[][]): number {
const n = nums.length;
const g = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const dfs = (u, fa) => {
let f0 = 0, f1 = -Infinity;
for (const v of g[u]) {
if (v !== fa) {
const [r0, r1] = dfs(v, u);
let t = Math.max(f1 + r0, f0 + r1);
f0 = Math.max(f0 + r0, f1 + r1);
f1 = t;
}
}
const x = nums[u], y = nums[u] ^ k;
return [Math.max(f0 + x, f1 + y), Math.max(f1 + x, f0 + y)];
};
return dfs(0, -1)[0];
};
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。树形动态规划需要遍历每一条边。
- 空间复杂度：$O(n)$，需要保存所有的边。
方法三：状态机动态规划
思路与算法
由于我们每次都选择两个点进行操作，因此任意时刻进行过奇数次异或操作的点的数量一定为偶数。问题转化为：
选择 $\textit{nums}$ 中的偶数个数，把它们都异或上 $k$，令数组的总和最大。
这个问题可以使用状态机动态规划解决。令 $f[i][0]$ 表示 $\textit{nums}$ 中的前 $i$ 个数中的偶数个数异或 $k$ 的最大元素和，$f[i][1]$ 表示 $\textit{nums}$ 中的前 $i$ 个数中的奇数个数异或 $k$ 的最大元素和。考虑是否操作 $\textit{nums}[i]$，则有转移方程：
$$
\begin{aligned}
f[i+1][0]&=\max(f[i][0]+\textit{nums}[i],f[i][1]+(\textit{nums}[i]\oplus k))\
f[i+1][1]&=\max(f[i][1]+\textit{nums}[i],f[i][0]+(\textit{nums}[i]\oplus k))
\end{aligned}
$$
初始值 $f[0][0]=0,f[0][1]=-\infty$，结果为 $f[n][0]$。可以使用滚动数组将第一维压缩。
代码
###C++
class Solution {
public:
long long maximumValueSum(vector<int> &nums, int k, vector<vector<int>> &edges) {
long long f0 = 0, f1 = LLONG_MIN;
for (int x : nums) {
long long t = max(f1 + x, f0 + (x ^ k));
f0 = max(f0 + x, f1 + (x ^ k));
f1 = t;
}
return f0;
}
};
###Java
class Solution {
public long maximumValueSum(int[] nums, int k, int[][] edges) {
long f0 = 0, f1 = Long.MIN_VALUE;
for (int x : nums) {
long t = Math.max(f1 + x, f0 + (x ^ k));
f0 = Math.max(f0 + x, f1 + (x ^ k));
f1 = t;
}
return f0;
}
}
###Python
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
f0, f1 = 0, -inf
for x in nums:
t = max(f1 + x, f0 + (x ^ k))
f0, f1 = max(f0 + x, f1 + (x ^ k)), t
return f0
###C
long long maximumValueSum(int* nums, int numsSize, int k, int** edges,
int edgesSize, int* edgesColSize) {
long long f0 = 0, f1 = LLONG_MIN;
for (int i = 0; i < numsSize; ++i) {
int x = nums[i];
long long t = f1 + x > f0 + (x ^ k) ? f1 + x : f0 + (x ^ k);
long long new_f0 = f0 + x > f1 + (x ^ k) ? f0 + x : f1 + (x ^ k);
f1 = t;
f0 = new_f0;
}
return f0;
}
###Golang
func maximumValueSum(nums []int, k int, edges [][]int) int64 {
var f0, f1 int64
f0, f1 = int64(0), math.MinInt64
for _, x := range nums {
f0, f1 = max(f0+int64(x), f1+int64(x^k)), max(f1+int64(x), f0+int64(x^k))
}
return f0
}
###C#
public class Solution {
public long MaximumValueSum(int[] nums, int k, int[][] edges) {
long f0 = 0, f1 = long.MinValue;
foreach (int x in nums) {
long t = Math.Max(f1 + x, f0 + (x ^ k));
f0 = Math.Max(f0 + x, f1 + (x ^ k));
f1 = t;
}
return f0;
}
}
###Rust
impl Solution {
pub fn maximum_value_sum(nums: Vec<i32>, k: i32, edges: Vec<Vec<i32>>) -> i64 {
let mut f0: i64 = 0;
let mut f1: i64 = i64::MIN;
for &x in &nums {
let xk = (x ^ k) as i64;
let x = x as i64;
let t = f1 + x;
let alt = f0 + xk;
let new_f0 = (f0 + x).max(f1 + xk);
f1 = t.max(alt);
f0 = new_f0;
}
f0
}
}
###JavaScript
var maximumValueSum = function (nums, k, edges) {
let f0 = 0, f1 = -Infinity;
for (const x of nums) {
const t = Math.max(f1 + x, f0 + (x ^ k));
f0 = Math.max(f0 + x, f1 + (x ^ k));
f1 = t;
}
return f0;
};
###TypeScript
function maximumValueSum(nums: number[], k: number, edges: number[][]): number {
let f0 = 0, f1 = -Infinity;
for (const x of nums) {
const t = Math.max(f1 + x, f0 + (x ^ k));
f0 = Math.max(f0 + x, f1 + (x ^ k));
f1 = t;
}
return f0;
};
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。
- 空间复杂度：$O(1)$。只需要若干额外变量。
