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 测试。