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