Kimi LeetCode 2322.从树中删除边的最小分数 C语言实现

这是 LeetCode 2322「从树中删除边的最小分数」的 C 语言实现。核心思路1. 建图用邻接表存储树的结构2. DFS 预处理以 0 为根节点计算每个节点的子树异或值 subXor[]同时记录进入/离开时间 in[]/out[] 用于判断祖先关系3. 枚举边对树有 n-1 条边每条边对应一个非根子树。枚举所有非根节点对 (u, v) 代表删除两条边根据祖先关系分三种情况计算三个连通块的异或值- u 是 v 的祖先三块为 subXor[v]、subXor[u]^subXor[v]、totalXor^subXor[u]- v 是 u 的祖先对称情况- 互不为祖先三块为 subXor[u]、subXor[v]、totalXor^subXor[u]^subXor[v]4. 取所有方案中 max - min 的最小值c#include stdio.h#include stdlib.h#include string.h#include limits.h// LeetCode 2322. 从树中删除边的最小分数// C 语言实现typedef struct {int *data;int size;int cap;} Vec;static void vec_init(Vec *v) {v-data NULL;v-size 0;v-cap 0;}static void vec_push(Vec *v, int x) {if (v-size v-cap) {v-cap v-cap ? v-cap * 2 : 4;v-data realloc(v-data, sizeof(int) * v-cap);}v-data[v-size] x;}static void vec_free(Vec *v) {free(v-data);v-data NULL;v-size v-cap 0;}// 全局变量static Vec *g; // 邻接表static int *in, *out; // DFS 时间戳static int *subXor; // 子树异或值static int timer;static int totalXor;static void dfs(int u, int p, const int *nums) {in[u] timer;subXor[u] nums[u];for (int i 0; i g[u].size; i) {int v g[u].data[i];if (v p) continue;dfs(v, u, nums);subXor[u] ^ subXor[v];}out[u] timer - 1;}// 判断 u 是否是 v 的祖先包含自身static int isAncestor(int u, int v) {return in[u] in[v] out[u] out[v];}// 求三个数的最大值static int max3(int a, int b, int c) {int m a b ? a : b;return m c ? m : c;}// 求三个数的最小值static int min3(int a, int b, int c) {int m a b ? a : b;return m c ? m : c;}int minimumScore(int *nums, int numsSize, int **edges, int edgesSize, int *edgesColSize) {int n numsSize;// 建图g malloc(sizeof(Vec) * n);for (int i 0; i n; i) vec_init(g[i]);for (int i 0; i edgesSize; i) {int a edges[i][0], b edges[i][1];vec_push(g[a], b);vec_push(g[b], a);}// 计算整棵树的总异或值totalXor 0;for (int i 0; i n; i) totalXor ^ nums[i];// 初始化数组in malloc(sizeof(int) * n);out malloc(sizeof(int) * n);subXor malloc(sizeof(int) * n);timer 0;// 以 0 为根进行 DFSdfs(0, -1, nums);int ans INT_MAX;// 枚举所有非根节点对每个非根节点代表其父边// 节点 0 是根没有父边所以从 1 开始for (int u 1; u n; u) {for (int v 1; v n; v) {if (u v) continue;int xor1, xor2, xor3;if (isAncestor(u, v)) {// u 是 v 的祖先xor1 subXor[v]; // v 的子树xor2 subXor[u] ^ subXor[v]; // u 的子树去掉 v 的子树xor3 totalXor ^ subXor[u]; // 剩余部分} else if (isAncestor(v, u)) {// v 是 u 的祖先xor1 subXor[u]; // u 的子树xor2 subXor[v] ^ subXor[u]; // v 的子树去掉 u 的子树xor3 totalXor ^ subXor[v]; // 剩余部分} else {// 互不为祖先xor1 subXor[u]; // u 的子树xor2 subXor[v]; // v 的子树xor3 totalXor ^ xor1 ^ xor2; // 剩余部分}int mx max3(xor1, xor2, xor3);int mn min3(xor1, xor2, xor3);int score mx - mn;if (score ans) ans score;}}// 释放内存for (int i 0; i n; i) vec_free(g[i]);free(g);free(in);free(out);free(subXor);return ans;}复杂度分析- 时间复杂度O(n^2)DFS 为 O(n)枚举节点对为 O(n^2)- 空间复杂度O(n)邻接表和时间戳数组关键说明1. 以 0 为根树是无向的但我们需要一个根来确定父子关系和子树范围。选择 0 作为根节点那么每个非根节点 u 到其父节点的边就是一条可被删除的边subXor[u] 就是删除该边后 u 所在连通块的异或值。2. 祖先判断通过 DFS 序 in/out 可以在 O(1) 时间内判断两棵子树的包含关系这是正确分类三种情况的基础。