Hard
题目描述
给你一个有 n 个节点的无向树，节点编号为 0 到 n - 1。树用长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间有一条无向边。
给你一个长度为 n 的字符串 s，由小写英文字母组成，其中 s[i] 表示分配给节点 i 的字符。
还给你一个字符串数组 queries，每个 queries[i] 是以下两种类型之一：
- “update ui c”：将节点 ui 处的字符改为 c。即更新 s[ui] = c。
- “query ui vi”：判断从 ui 到 vi 的唯一路径上的字符组成的字符串（包括端点）是否可以重新排列成回文串。
返回一个布尔数组 answer，其中 answer[j] 为 true 当且仅当第 j 个类型为 “query ui vi” 的查询可以重新排列成回文串，否则为 false。
示例 1：
输入：n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]
输出：[true,false]
解释：
- "query 0 2"：路径 0 → 1 → 2 给出 "aac"，可以重新排列成回文串 "aca"。因此 answer[0] = true。
- "update 1 b"：将节点 1 更新为 'b'，现在 s = "abc"。
- "query 0 2"：路径字符为 "abc"，无法重新排列成回文串。因此 answer[1] = false。
示例 2：
输入：n = 4, edges = [[0,1],[0,2],[0,3]], s = "abca", queries = ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]
输出：[false,false,true]
约束条件：
- 1 <= n == s.length <= 5 * 10^4
- edges.length == n - 1
- 0 <= ui, vi <= n - 1
- s 由小写英文字母组成
- 输入保证 edges 表示一个有效的树
- 1 <= queries.length <= 5 * 10^4
解题思路
这道题的核心思路是使用重链剖分（Heavy-Light Decomposition）和位掩码（Bitmask）来高效处理树上路径查询。
关键观察：
- 一个字符串能重新排列成回文串，当且仅当最多有一个字符出现奇数次
- 可以用 26 位的位掩码表示每个字符的奇偶性状态
- 路径上所有字符的异或结果，如果最多有 1 位为 1，则可以形成回文
解决方案：
- 重链剖分：将树分解为若干条重链，使得任意路径最多跨越 O(log n) 条链
- 线段树维护：对每条重链建立线段树，维护区间异或值
- 位掩码表示：每个字符对应一个位，字符 ‘a’ 对应第 0 位，‘b’ 对应第 1 位，以此类推
- 路径查询：将路径分解为多个重链段，分别查询并异或所有结果
算法步骤：
- 构建邻接表并进行重链剖分
- 为每条重链建立线段树，支持单点更新和区间查询
- 对于查询操作，找到两点间的路径，分解为重链段
- 异或所有段的结果，检查是否最多有 1 位为 1
时间复杂度为 O(q log n)，其中 q 是查询数量。
代码实现
class Solution {
private:
vector<vector<int>> adj;
vector<int> parent, depth, heavy, head, pos;
vector<int> segTree;
int timer;
void dfs1(int u, int p) {
int size = 1, maxChild = 0;
for (int v : adj[u]) {
if (v != p) {
parent[v] = u;
depth[v] = depth[u] + 1;
dfs1(v, u);
size += 1;
if (maxChild == 0) {
maxChild = 1;
heavy[u] = v;
}
}
}
}
void dfs2(int u, int h) {
head[u] = h;
pos[u] = timer++;
if (heavy[u] != -1) {
dfs2(heavy[u], h);
}
for (int v : adj[u]) {
if (v != parent[u] && v != heavy[u]) {
dfs2(v, v);
}
}
}
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
segTree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node, start, mid, idx, val);
} else {
update(2 * node + 1, mid + 1, end, idx, val);
}
segTree[node] = segTree[2 * node] ^ segTree[2 * node + 1];
}
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return segTree[node];
int mid = (start + end) / 2;
return query(2 * node, start, mid, l, r) ^ query(2 * node + 1, mid + 1, end, l, r);
}
int queryPath(int u, int v) {
int result = 0;
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
result ^= query(1, 0, timer - 1, pos[head[u]], pos[u]);
u = parent[head[u]];
}
if (depth[u] > depth[v]) swap(u, v);
result ^= query(1, 0, timer - 1, pos[u], pos[v]);
return result;
}
bool canFormPalindrome(int mask) {
return __builtin_popcount(mask) <= 1;
}
public:
vector<bool> palindromePath(int n, vector<vector<int>>& edges, string s, vector<string>& queries) {
adj.resize(n);
parent.resize(n);
depth.resize(n);
heavy.assign(n, -1);
head.resize(n);
pos.resize(n);
segTree.resize(4 * n);
timer = 0;
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
depth[0] = 0;
dfs1(0, -1);
dfs2(0, 0);
for (int i = 0; i < n; i++) {
update(1, 0, timer - 1, pos[i], 1 << (s[i] - 'a'));
}
vector<bool> result;
for (string& q : queries) {
if (q[0] == 'u') {
int space1 = q.find(' ');
int space2 = q.find(' ', space1 + 1);
int u = stoi(q.substr(space1 + 1, space2 - space1 - 1));
char c = q[space2 + 1];
update(1, 0, timer - 1, pos[u], 1 << (c - 'a'));
} else {
int space1 = q.find(' ');
int space2 = q.find(' ', space1 + 1);
int u = stoi(q.substr(space1 + 1, space2 - space1 - 1));
int v = stoi(q.substr(space2 + 1));
int mask = queryPath(u, v);
result.push_back(canFormPalindrome(mask));
}
}
return result;
}
};
class Solution:
def palindromePath(self, n: int, edges: list[list[int]], s: str, queries: list[str]) -> list[bool]:
from collections import defaultdict
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
parent = [-1] * n
depth = [0] * n
heavy = [-1] * n
head = [0] * n
pos = [0] * n
timer = [0]
def dfs1(u, p):
size = 1
max_child_size = 0
for v in adj[u]:
if v != p:
parent[v] = u
depth[v] = depth[u] + 1
child_size = dfs1(v, u)
size += child_size
if child_size > max_child_size:
max_child_size = child_size
heavy[u] = v
return size
def dfs2(u, h):
head[u] = h
pos[u] = timer[0]
timer[0] += 1
if heavy[u] != -1:
dfs2(heavy[u], h)
for v in adj[u]:
if v != parent[u] and v != heavy[u]:
dfs2(v, v)
dfs1(0, -1)
dfs2(0, 0)
seg_tree = [0] * (4 * n)
def update(node, start, end, idx, val):
if start == end:
seg_tree[node] = val
else:
mid = (start + end) // 2
if idx <= mid:
update(2 * node, start, mid, idx, val)
else:
update(2 * node + 1, mid + 1, end, idx, val)
seg_tree[node] = seg_tree[2 * node] ^ seg_tree[2 * node + 1]
def query(node, start, end, l, r):
if r < start or end < l:
return 0
if l <= start and end <= r:
return seg_tree[node]
mid = (start + end) // 2
return query(2 * node, start, mid, l, r) ^ query(2 * node + 1, mid + 1, end, l, r)
def query_path(u, v):
result = 0
while head[u] != head[v]:
if depth[head[u]] < depth[head[v]]:
u, v = v, u
result ^= query(1, 0, n - 1, pos[head[u]], pos[u])
u = parent[head[u]]
if depth[u] > depth[v]:
u, v = v, u
result ^= query(1, 0, n - 1, pos[u], pos[v])
return result
for i in range(n):
update(1, 0, n - 1, pos[i], 1 << (ord(s[i]) - ord('a')))
result = []
for q in queries:
parts = q.split()
if parts[0] == "update":
u = int(parts[1])
c = parts[2]
update(1, 0, n - 1, pos[u], 1 << (ord(c) - ord('a')))
else:
u = int(parts[1])
v = int(parts[2])
mask = query_path(u, v)
result.append(bin(mask).count('1') <= 1)
return result
public class Solution {
private List<int>[] adj;
private int[] parent, depth, heavy, head, pos;
private int[] segTree;
private int timer;
private void Dfs1(int u, int p) {
int size = 1, maxChildSize = 0;
foreach (int v in adj[u]) {
if (v != p) {
parent[v] = u;
depth[v] = depth[u] + 1;
int childSize = Dfs1(v, u);
size += childSize;
if (childSize > maxChildSize) {
maxChildSize = childSize;
heavy[u] = v;
}
}
}
return size;
}
private void Dfs2(int u, int h) {
head[u] = h;
pos[u] = timer++;
if (heavy[u] != -1) {
Dfs2(heavy[u], h);
}
foreach (int v in adj[u]) {
if (v != parent[u] && v != heavy[u]) {
Dfs2(v, v);
}
}
}
private void Update(int node, int start, int end, int idx, int val) {
if (start == end) {
segTree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
Update(2 * node, start, mid, idx, val);
} else {
Update(2 * node + 1, mid + 1, end, idx, val);
}
segTree[node] = segTree[2 * node] ^ segTree[2 * node + 1];
}
}
private int Query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return segTree[node];
int mid = (start + end) / 2;
return Query(2 * node, start, mid, l, r) ^ Query(2 * node + 1, mid + 1, end, l, r);
}
private int QueryPath(int u, int v) {
int result = 0;
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) {
(u, v) = (v, u);
}
result ^= Query(1, 0, timer - 1, pos[head[u]], pos[u]);
u = parent[head[u]];
}
if (depth[u] > depth[v]) {
(u, v) = (v, u);
}
result ^= Query(1, 0, timer - 1, pos[u], pos[v]);
return result;
}
public IList<bool> PalindromePath(int n, int[][] edges, string s, string[] queries) {
adj = new List<int>[n];
for (int i = 0; i < n; i++) {
adj[i] = new List<int>();
}
foreach (var edge in edges) {
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
}
parent = new int[n];
depth = new int[n];
heavy = Enumerable.Repeat(-1, n).ToArray();
head = new int[n];
pos = new int[n];
segTree = new int[4 * n];
timer = 0;
Dfs1(0, -1);
Dfs2(0, 0);
for (int i = 0; i < n; i++) {
Update(1, 0, timer - 1, pos[i], 1 << (s[i] - 'a'));
}
var result = new List<bool>();
foreach (string q in queries) {
string[] parts = q.Split(' ');
if (parts[0] == "update") {
int u = int.Parse(parts[1]);
char c = parts[2][0];
Update(1, 0, timer - 1, pos[u], 1 << (c - 'a'));
} else {
int u = int.Parse(parts[1]);
int v = int.Parse(parts[2]);
int mask = QueryPath(u, v);
result.Add(System.Numerics.BitOperations.PopCount((uint)mask) <= 1);
}
}
return result;
}
}
var palindromePath = function(n, edges, s, queries) {
const adj = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const chars = s.split('');
const result = [];
const findPath = (start, end) => {
if (start === end) return [start];
const visited = new Set();
const parent = new Map();
const queue = [start];
visited.add(start);
while (queue.length > 0) {
const node = queue.shift();
if (node === end) break;
for (const neighbor of adj[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
parent.set(neighbor, node);
queue.push(neighbor);
}
}
}
const path = [];
let current = end;
while (current !== undefined) {
path.unshift(current);
current = parent.get(current);
}
return path;
};
const canFormPalindrome = (path) => {
const charCount = {};
for (const node of path) {
const char = chars[node];
charCount[char] = (charCount[char] || 0) + 1;
}
let oddCount = 0;
for (const count of Object.values(charCount)) {
if (count % 2 === 1) oddCount++;
}
return oddCount <= 1;
};
for (const query of queries) {
const parts = query.split(' ');
if (parts[0] === 'update') {
const node = parseInt(parts[1]);
const newChar = parts[2];
chars[node] = newChar;
} else {
const u = parseInt(parts[1]);
const v = parseInt(parts[2]);
const path = findPath(u, v);
result.push(canFormPalindrome(path));
}
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n + q log n) | 其中 n 为节点数，q 为查询数。重链剖分预处理 O(n)，每次查询或更新 O(log n) |
| 空间复杂度 | O(n) | 存储树结构、重链剖分信息和线段树 |