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递归对抗引擎优化：贝叶斯决策迭代收敛参数与混沌不确定性量化机制深度研究

更多资讯

Wagtail 6.0.2 发布说明深度解析：Chooser 模态框、ModelViewSet 与 TableBlock 的 8 项关键修复

Waybar 日历周数显示错位、算错？这份快速修复指南一次讲清

pykan 实战：用 KAN 从二维哈密顿流场中无监督学习守恒律（Conservation Laws）

Megatron-LM 大型 PR 拆分实战：基于 CODEOWNERS 分组的最小审查集合拆分指南

amis 页面交互行为跟踪（tracker）实战指南：从采集到上报的完整方案

ClickHouse v21.7.3.14-stable 深度解析：从七个 Bug 修复看分布式查询与几何函数的内核细节

今日更新

51单片机开环控制磁阻传感器的硬件匹配与代码实现

AI Agent安全操作数据库：SQL注入防御与参数化查询实战

Android逆向实战：还原激励类App签到接口的签名算法

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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