leetcode每日一题(好几天之前的) -- 3068.最大节点价值之和
思路
一开始,我是想利用异或的特性,重复异或两次变为原值,那么只要异或后的值更大,就更新
- 但是这和题意相违背,因为题目做处理是对边整体进行的 (我写的版本是对顶点分别控制的)
但即使加上一起变动的特性,这个思路也是不对的
- 如果一个顶点有多条边相连 & 当前已经对[先遍历到的边]异或过
- 那么到了同顶点的其他边时就无法再变动了 -- 因为异或后会变小(变为原值),但是可能这里对另一个顶点异或后会带来全局的更优解
总之还是去看了题解
贪心
梳理一下题意
- 规定是可以对相邻两个节点同时进行异或操作,但是树中任意两个节点之间都是可以联通的(树 -- 无环且连通的无向图)
- 所以如果对一条路径上的所有边都进行异或操作,最终只有路径端点被异或,其他节点都没变(异或两次恢复了)
- 于是,原先的 [只有相邻节点可以被异或] 可以转换成 [对任意两个节点异或]
于是,可以先对每个节点进行异或,计算出和原来相比的差值
- 如果差值为正,说明异或后可以使总和变大,那么就加入到结果中
- 既然要求和的最大值 & 可以对任意两点进行异或,那就直接按差值排序,然后再成对使用
树形dp
递归
本题中,每个节点有两种选择：异或该节点 / 不异或该节点
- 而这里的选择取决于该节点的子节点选择了什么,子节点的选择又取决于孙子节点...
- 于是形成了自顶向下的依赖关系,所以最好是使用递归逻辑
预处理
将原先给定边的形式,转换为邻接表
- 方便后续的递归操作(dfs)
未完待续....
代码
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;}
};class Solution {// dfs函数返回一个pair<long long, long long>：// first -> 当前节点u“不进行异或操作”时，子树的最大价值和// second -> 当前节点u“进行异或操作”时，子树的最大价值和pair<long long, long long> dfs(int node, int parent,const vector<vector<int>>& graph,const vector<int>& nums, int k) {long long sumIfNotXor = 0;long long sumIfXor = LLONG_MIN;for (int child : graph[node]) {//if (child == parent)continue;auto [childNotXor, childXor] = dfs(child, node, graph, nums, k);long long newSumIfXor =max(sumIfXor + childNotXor, sumIfNotXor + childXor);long long newSumIfNotXor =max(sumIfNotXor + childNotXor, sumIfXor + childXor);sumIfXor = newSumIfXor;sumIfNotXor = newSumIfNotXor;}long long resultNotXor =max(sumIfNotXor + nums[node], sumIfXor + (nums[node] ^ k));long long resultXor =max(sumIfXor + nums[node], sumIfNotXor + (nums[node] ^ k));return {resultNotXor, resultXor};}public:long long maximumValueSum(vector<int>& nums, int k,vector<vector<int>>& edges) {int n = (int)nums.size();vector<vector<int>> graph(n);// 建图，邻接表形式for (auto& edge : edges) {int u = edge[0], v = edge[1];graph[u].push_back(v);graph[v].push_back(u);}// 从根节点0开始DFS，返回两个状态的最大值，我们要的是未异或状态的最大值return dfs(0, -1, graph, nums, k).first;}
};