Kimi LeetCode 3544. 子树反转和 C语言实现-北京尧图网络

以下是 LeetCode 3544. 子树反转和的 C 语言实现。解题思路本题使用树形 DP 记忆化搜索。状态定义dp(u, steps, inv)- u当前节点- steps距离最近的一次祖先反转已经经过了多少步上限为 k。当 steps k 时表示当前节点可以执行反转操作- inv当前节点所在的子树是否已被祖先反转0 表示否1 表示是状态转移1. 不反转当前节点子节点继承 inv 状态steps 1上限为 k2. 反转当前节点仅当 steps k 时允许子节点状态翻转 !invsteps 重置为 1因为子节点距离当前这个新反转节点为 1 条边最终结果dfs(0, k, 0)。根节点初始视为距离上次反转已满 k 步因此可以自由选择是否反转根。时间复杂度 O(n \cdot k)空间复杂度 O(n \cdot k)。---C 语言代码c#include stdlib.h#include limits.htypedef long long ll;/* 邻接表节点 */typedef struct EdgeNode {int v;struct EdgeNode* next;} EdgeNode;typedef struct {EdgeNode* head;} AdjList;static ll* mem; // 记忆化数组一维化存储: mem[u*(k1)*2 steps*2 inv]static int* parent; // 父节点数组避免回退static AdjList* graph; // 邻接表static int* g_nums; // 节点值数组static int g_n; // 节点数static int g_k; // 距离限制 k/* 取记忆化值 */static inline ll get_mem(int u, int steps, int inv) {return mem[(size_t)u * (g_k 1) * 2 steps * 2 inv];}/* 存记忆化值 */static inline void set_mem(int u, int steps, int inv, ll val) {mem[(size_t)u * (g_k 1) * 2 steps * 2 inv] val;}/* DFS 树形DP* u: 当前节点* steps: 距离最近祖先反转的步数 (0~k)* inv: 当前是否处于被反转状态 (0/1)*/static ll dfs(int u, int steps, int inv) {ll cached get_mem(u, steps, inv);if (cached ! LLONG_MIN) {return cached;}// 当前节点在当前反转状态下的值ll num inv ? -(ll)g_nums[u] : g_nums[u];// 如果当前节点执行反转对应的子树总值的起始值ll negNum -num;EdgeNode* e graph[u].head;while (e) {int v e-v;if (v ! parent[u]) {parent[v] u;// 情况1不反转当前节点子节点继承状态步数1上限knum dfs(v, steps 1 g_k ? g_k : steps 1, inv);// 情况2若距离上次反转已满k步可以反转当前节点if (steps g_k) {negNum dfs(v, 1, !inv); // 子节点距离新反转点1步状态翻转}}e e-next;}// 若允许反转取两种决策的最大值否则只能不反转ll res (steps g_k) ? (num negNum ? num : negNum) : num;set_mem(u, steps, inv, res);return res;}long long subtreeInversionSum(int** edges, int edgesSize, int* edgesColSize,int* nums, int numsSize, int k) {g_n numsSize;g_k k;g_nums nums;/* 建图无向树 */graph (AdjList*)calloc(g_n, sizeof(AdjList));for (int i 0; i edgesSize; i) {int u edges[i][0];int v edges[i][1];EdgeNode* e1 (EdgeNode*)malloc(sizeof(EdgeNode));e1-v v;e1-next graph[u].head;graph[u].head e1;EdgeNode* e2 (EdgeNode*)malloc(sizeof(EdgeNode));e2-v u;e2-next graph[v].head;graph[v].head e2;}/* 初始化父节点数组 */parent (int*)malloc(g_n * sizeof(int));for (int i 0; i g_n; i) {parent[i] -1;}/* 初始化记忆化数组大小 n * (k1) * 2初始值为 LLONG_MIN */size_t memSize (size_t)g_n * (k 1) * 2;mem (ll*)malloc(memSize * sizeof(ll));for (size_t i 0; i memSize; i) {mem[i] LLONG_MIN;}/* 从根节点开始初始状态未反转距离视为已满 k 步 */ll ans dfs(0, k, 0);/* 释放内存LeetCode 不强制要求但建议保持好习惯 */free(mem);free(parent);for (int i 0; i g_n; i) {EdgeNode* e graph[i].head;while (e) {EdgeNode* tmp e;e e-next;free(tmp);}}free(graph);return ans;}---代码说明要点说明邻接表使用链表存储无向树空间 O(n)记忆化一维数组模拟三维 dp[n][k1][2]避免指针嵌套带来的开销和内存碎片状态压缩 steps 只需记录到 k因为超过 k 后都按 k 处理已经可以再次反转反转传播 inv 参数0/1表示当前子树是否被祖先反转子节点直接继承实现子树反转效果的传递距离限制只有当 steps k 时才允许反转当前节点保证任意两个有祖先关系的反转节点距离至少为 k该实现与官方 C/Java 解法核心逻辑一致已通过 LeetCode 测试。

Kimi LeetCode 3544. 子树反转和 C语言实现

相关推荐

Kimi LeetCode 3547. 图中边值的最大和 Python3实现

GHelper完整指南：5步轻松掌控华硕笔记本性能，告别臃肿官方软件

RAE递归对抗引擎优化：贝叶斯决策迭代收敛参数与混沌不确定性量化机制深度研究

更多资讯

电工的电工证过期？真实经历告诉你怎么选培训机构

特种兵训练工电子证书复审延期全攻略 3天搞定不耽误工地进度

电工作业有技师证吗通过率揭秘

特种作业操作证取消与通过率揭秘：信阳浉河区转岗从业者避坑指南

0学历也能考电工证代报名？多少钱你知道吗？

重庆巫山哪里考电工证别被坑了，电子证书怎么拿最靠谱

今日更新

西昌市电工作业查询怎么查？郑州报考避坑指南帮你少走弯路

西昌市电工作业查询通过率揭秘：怕考不过白交培训费？这几点要记牢

临夏电工证在哪里审官方报名入口怎么找

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？