当前位置：首页 > news >正文

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

news 2026/8/7 0:54:48

解题思路

核心在于快速判断树中任意两点路径上的字符能否重排为回文串。

· 回文判定：一个字符串能重排成回文，当且仅当其出现奇数次的字符最多只有一个。
用 26 位整数（掩码）表示每个字符的奇偶性：第 i 位为 1 表示字符 i 出现奇数次。
· 前缀异或（XOR）
定义 pref[x] 为从根节点到 x 的路径上所有字符的奇偶掩码。
则 u 到 v 路径的掩码为：
mask(u→v) = pref[u] ^ pref[v] ^ (1 << char(LCA(u,v)))。
· 动态更新
修改节点 u 的字符时，会影响以 u 为根的整棵子树中所有节点的 pref 值。
利用 DFS 序（欧拉序）将子树映射为连续区间 [tin[u], tout[u]]，再用树状数组（Fenwick Tree）维护区间异或更新和单点查询。
· LCA 查询：使用二进制提升（Binary Lifting）预处理，O(log n) 回答。

---

Rust 实现

```rust
struct BIT {
bit: Vec<u32>,
n: usize,
}

impl BIT {
fn new(n: usize) -> Self {
BIT {
bit: vec![0; n + 2],
n,
}
}

fn add(&mut self, mut idx: usize, val: u32) {
while idx <= self.n {
self.bit[idx] ^= val;
idx += idx & idx.wrapping_neg(); // lowbit
}
}

// 区间 [l, r] 异或 val
fn range_xor(&mut self, l: usize, r: usize, val: u32) {
self.add(l, val);
self.add(r + 1, val);
}

// 单点查询
fn query(&self, mut idx: usize) -> u32 {
let mut res = 0;
while idx > 0 {
res ^= self.bit[idx];
idx -= idx & idx.wrapping_neg();
}
res
}
}

impl Solution {
pub fn palindrome_path(n: i32, edges: Vec<Vec<i32>>, s: String, queries: Vec<String>) -> Vec<bool> {
let n = n as usize;
// 建图
let mut g = vec![Vec::new(); n];
for e in edges {
let u = e[0] as usize;
let v = e[1] as usize;
g[u].push(v);
g[v].push(u);
}

let s_bytes = s.as_bytes();
let mut depth = vec![0; n];
let mut tin = vec![0; n];
let mut tout = vec![0; n];
let mut pref = vec![0u32; n];
let mut parent = vec![vec![0; n]; 1]; // 第一层，后续扩展

// ---------- 迭代 DFS 计算 tin, tout, depth, parent[0], pref ----------
let mut stack = Vec::new();
stack.push((0, -1, 0)); // (节点, 父节点, 状态) 状态0=进入, 1=离开
let mut timer = 0;
while let Some((u, p, state)) = stack.pop() {
if state == 0 {
timer += 1;
tin[u] = timer;
if p == -1 {
depth[u] = 0;
parent[0][u] = 0;
pref[u] = 1u32 << (s_bytes[u] - b'a');
} else {
let p = p as usize;
depth[u] = depth[p] + 1;
parent[0][u] = p;
pref[u] = pref[p] ^ (1u32 << (s_bytes[u] - b'a'));
}
stack.push((u, p, 1)); // 退出标记
for &v in &g[u] {
if p == -1 || v != p as usize {
stack.push((v, u as i32, 0));
}
}
} else {
tout[u] = timer;
}
}

// ---------- 二进制提升表 ----------
let mut LOG = 1;
while (1 << LOG) <= n {
LOG += 1;
}
parent.resize(LOG, vec![0; n]);
for k in 1..LOG {
for i in 0..n {
parent[k][i] = parent[k - 1][parent[k - 1][i]];
}
}

// LCA 闭包
let lca = |mut u: usize, mut v: usize| -> usize {
if depth[u] < depth[v] {
std::mem::swap(&mut u, &mut v);
}
let diff = depth[u] - depth[v];
for k in 0..LOG {
if diff & (1 << k) != 0 {
u = parent[k][u];
}
}
if u == v {
return u;
}
for k in (0..LOG).rev() {
if parent[k][u] != parent[k][v] {
u = parent[k][u];
v = parent[k][v];
}
}
parent[0][u]
};

let mut bit = BIT::new(n);
let mut chars: Vec<u8> = s_bytes.iter().map(|&b| b - b'a').collect();
let mut ans = Vec::new();

for q in queries {
let parts: Vec<&str> = q.split_whitespace().collect();
match parts[0] {
"update" => {
let u = parts[1].parse::<usize>().unwrap();
let c = parts[2].as_bytes()[0] - b'a';
if c != chars[u] {
let diff = (1u32 << chars[u]) ^ (1u32 << c);
bit.range_xor(tin[u], tout[u], diff);
chars[u] = c;
}
}
"query" => {
let u = parts[1].parse::<usize>().unwrap();
let v = parts[2].parse::<usize>().unwrap();
let w = lca(u, v);
let cur_u = pref[u] ^ bit.query(tin[u]);
let cur_v = pref[v] ^ bit.query(tin[v]);
let mask = cur_u ^ cur_v ^ (1u32 << chars[w]);
// 判断 mask 是否只有 0 或 1 个 1
ans.push((mask & (mask - 1)) == 0);
}
_ => {}
}
}
ans
}
}
```