DeepSeek LeetCode 3841. 查询树上回文路径 Java实现

解题思路

这道题的核心在于如何高效判断树中任意两点路径上的字符能否重排为回文串。

回文串的判定条件：一个字符串能重排成回文串，当且仅当其出现奇数次的字符最多只有一个。例如 "aac" 中 a 出现2次（偶），c 出现1次（奇），可重排为 "aca"。

核心优化技巧——前缀异或（Prefix XOR）与位掩码：

· 用26位整数（int）的二进制位表示每个字符的奇偶性。某位为1表示对应字符出现奇数次，0表示偶数次。
· 定义 mask[node] 为从根节点到该节点路径上所有字符的奇偶掩码。
· 树上两点 u 和 v 之间路径的奇偶掩码计算公式为：
mask(u→v) = mask(u) XOR mask(v) XOR (1 << char(lca(u, v)))
其中 lca(u, v) 是 u 和 v 的最近公共祖先。

处理更新操作：节点字符变更时，只需更新以该节点为根的整棵子树的 mask 值。利用 DFS序（欧拉序） 将子树转化为连续区间，再用 树状数组（Fenwick Tree） 维护区间异或和与单点查询。

---

Java 实现代码

```java
import java.util.*;

public class Solution {
// 链式前向星存图
private int[] head, to, nxt;
// 二进制提升（LCA）
private int[][] up;
private int[] depth;
// DFS序（欧拉序）
private int[] in, out;
private int timer;
private int maxLog;
// 树状数组
private BIT bit;
// 当前字符数组
private char[] chars;

public List<Boolean> palindromePath(int n, int[][] edges, String s, String[] queries) {
chars = s.toCharArray();
// 1. 建图
buildGraph(n, edges);

// 2. DFS预处理：深度、父节点、DFS序
maxLog = 31 - Integer.numberOfLeadingZeros(n);
up = new int[maxLog + 1][n];
depth = new int[n];
in = new int[n];
out = new int[n];
timer = 0;
dfs(0, -1);

// 3. 二进制提升表
for (int k = 1; k <= maxLog; k++) {
for (int i = 0; i < n; i++) {
up[k][i] = up[k - 1][up[k - 1][i]];
}
}

// 4. 树状数组维护每个节点的前缀掩码
bit = new BIT(n + 2);
for (int i = 0; i < n; i++) {
int mask = 1 << (chars[i] - 'a');
bit.rangeXor(in[i], out[i], mask);
}

// 5. 处理查询
List<Boolean> ans = new ArrayList<>();
for (String query : queries) {
if (query.startsWith("update")) {
// 解析：update ui c
int space1 = query.indexOf(' ');
int space2 = query.indexOf(' ', space1 + 1);
int u = Integer.parseInt(query.substring(space1 + 1, space2));
char c = query.charAt(space2 + 1);
if (c != chars[u]) {
int oldMask = 1 << (chars[u] - 'a');
int newMask = 1 << (c - 'a');
int diff = oldMask ^ newMask; // 变化的位
bit.rangeXor(in[u], out[u], diff);
chars[u] = c;
}
} else {
// 解析：query u v
int space1 = query.indexOf(' ');
int space2 = query.indexOf(' ', space1 + 1);
int u = Integer.parseInt(query.substring(space1 + 1, space2));
int v = Integer.parseInt(query.substring(space2 + 1));
int l = lca(u, v);
// 路径掩码 = mask(u) ^ mask(v) ^ char(lca)
int mask = bit.pointQuery(in[u]) ^ bit.pointQuery(in[v]) ^ (1 << (chars[l] - 'a'));
// 判断是否只有0个或1个1
ans.add((mask & (mask - 1)) == 0);
}
}
return ans;
}

// ---------- 建图 ----------
private void buildGraph(int n, int[][] edges) {
int m = edges.length;
head = new int[n];
Arrays.fill(head, -1);
to = new int[m * 2];
nxt = new int[m * 2];
for (int i = 0; i < m; i++) {
int u = edges[i][0], v = edges[i][1];
to[i * 2] = v;
nxt[i * 2] = head[u];
head[u] = i * 2;
to[i * 2 + 1] = u;
nxt[i * 2 + 1] = head[v];
head[v] = i * 2 + 1;
}
}

// ---------- DFS：深度、父节点、DFS序 ----------
private void dfs(int u, int parent) {
in[u] = ++timer;
up[0][u] = parent == -1 ? 0 : parent;
for (int e = head[u]; e != -1; e = nxt[e]) {
int v = to[e];
if (v == parent) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
out[u] = timer;
}

// ---------- LCA：二进制提升 ----------
private int lca(int u, int v) {
if (depth[u] < depth[v]) {
int tmp = u; u = v; v = tmp;
}
// 提升u到与v同深度
int diff = depth[u] - depth[v];
for (int k = maxLog; k >= 0; k--) {
if ((diff & (1 << k)) != 0) {
u = up[k][u];
}
}
if (u == v) return u;
for (int k = maxLog; k >= 0; k--) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
return up[0][u];
}

// ---------- 树状数组（支持区间异或、单点查询） ----------
static class BIT {
int n;
int[] tree;

BIT(int n) { this.n = n; tree = new int[n + 1]; }

void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx) tree[idx] ^= val;
}

// 区间 [l, r] 异或上 val
void rangeXor(int l, int r, int val) {
add(l, val);
add(r + 1, val);
}

// 单点查询
int pointQuery(int idx) {
int res = 0;
for (; idx > 0; idx -= idx & -idx) res ^= tree[idx];
return res;
}
}
}
```

代码解释

1. dfs预处理：计算每个节点的深度、父节点和 DFS 进入/退出时间戳。同一子树的节点在 in 和 out 之间形成连续区间。
2. BIT 树状数组：维护每个节点对应的前缀奇偶掩码（从根到该节点）。rangeXor(in[u], out[u], mask) 将 u 的整棵子树所有节点的前缀掩码异或上 mask。
3. 查询处理：
· 用 pointQuery(in[u]) 获取 mask(u)。
· 计算路径掩码：mask(u) ^ mask(v) ^ (1 << char(lca))。
· 判断 (mask & (mask - 1)) == 0，即二进制中是否只有0个或1个1。
4. 更新处理：字符从 old 变为 new 时，diff = (1<<old) ^ (1<<new) 表示变化的位，对 u 的子树区间异或 diff 即可。