/**
* 我们可以在 DFS 一棵树的过程中，维护一个全局的时间戳 clock，每访问一个新的节点，
* 就将 clock 加一。同时，记录进入节点 x 时的时间戳 in[x]，
* 和离开（递归结束）这个节点时的时间戳 out[x]。
*/
func minimumScore(nums []int, edges [][]int) int {
n := len(nums)
g := make([][]int, n)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
xor := make([]int, n)
in := make([]int, n)
out := make([]int, n)
clock := 0
var dfs func(int, int)
dfs = func(x, fa int) {
clock++
in[x] = clock
xor[x] = nums[x]
for _, y := range g[x] {
if y != fa {
dfs(y, x)
xor[x] ^= xor[y]
}
}
out[x] = clock
}
dfs(0, -1)
isAncestor := func(x, y int) bool { return in[x] < in[y] && in[y] <= out[x] }
ans := math.MaxInt32
for i := 2; i < n; i++ {
for j := 1; j < i; j++ {
var x, y, z int
if isAncestor(i, j) { // i 是 j 的祖先节点
x, y, z = xor[j], xor[i]^xor[j], xor[0]^xor[i]
} else if isAncestor(j, i) { // j 是 i 的祖先节点
x, y, z = xor[i], xor[i]^xor[j], xor[0]^xor[j]
} else { // 删除的两条边分别属于两颗不相交的子树
x, y, z = xor[i], xor[j], xor[0]^xor[i]^xor[j]
}
ans = min(ans, max(max(x, y), z)-min(min(x, y), z))
if ans == 0 {
return 0 // 提前退出
}
}
}
return ans
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
class Solution {
List<Integer>[] g;
int[] nums, xor, in, out;
int clock;
public int minimumScore(int[] nums, int[][] edges) {
var n = nums.length;
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x);
}
this.nums = nums;
xor = new int[n];
in = new int[n];
out = new int[n];
dfs(0, -1);
var ans = Integer.MAX_VALUE;
for (int i = 2, x, y, z; i < n; ++i)
for (var j = 1; j < i; ++j) {
if (in[i] < in[j] && in[j] <= out[i]) { // i 是 j 的祖先节点
x = xor[j];
y = xor[i] ^ x;
z = xor[0] ^ xor[i];
} else if (in[j] < in[i] && in[i] <= out[j]) { // j 是 i 的祖先节点
x = xor[i];
y = xor[j] ^ x;
z = xor[0] ^ xor[j];
} else { // 删除的两条边分别属于两颗不相交的子树
x = xor[i];
y = xor[j];
z = xor[0] ^ x ^ y;
}
ans = Math.min(ans, Math.max(Math.max(x, y), z) - Math.min(Math.min(x, y), z));
if (ans == 0) return 0; // 提前退出
}
return ans;
}
void dfs(int x, int fa) {
in[x] = ++clock;
xor[x] = nums[x];
for (var y : g[x])
if (y != fa) {
dfs(y, x);
xor[x] ^= xor[y];
}
out[x] = clock;
}
}
class Solution:
def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
n = len(nums)
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
xor, in_, out, clock = [0] * n, [0] * n, [0] * n, 0
def dfs(x: int, fa: int) -> None:
nonlocal clock
clock += 1
in_[x] = clock
xor[x] = nums[x]
for y in g[x]:
if y != fa:
dfs(y, x)
xor[x] ^= xor[y]
out[x] = clock
dfs(0, -1)
ans = inf
for i in range(2, n):
for j in range(1, i):
if in_[i] < in_[j] <= out[i]: # i 是 j 的祖先节点
x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]
elif in_[j] < in_[i] <= out[j]: # j 是 i 的祖先节点
x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]
else: # 删除的两条边分别属于两颗不相交的子树
x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]
ans = min(ans, max(x, y, z) - min(x, y, z))
# 注：把 min max 拆开，改为下面的注释，可以明显加快速度
# mn = mx = x
# if y < mn: mn = y
# elif y > mx: mx = y
# if z < mn: mn = z
# elif z > mx: mx = z
# if mx - mn < ans: ans = mx - mn
if ans == 0: return 0 # 提前退出
return ans
