这是 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 为根进行 DFS
dfs(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) 时间内判断两棵子树的包含关系，这是正确分类三种情况的基础。
