You are given an undirected tree with n nodes labeled 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.
You are also given a string s of length n consisting of lowercase English letters, where s[i] represents the character assigned to node i.
You are also given a string array queries, where each queries[i] is either:
"update ui c": Change the character at node ui to c. Formally, update s[ui] = c.
"query ui vi": Determine whether the string formed by the characters on the unique path from ui to vi (inclusive) can be rearranged into a palindrome.
Return a boolean array answer, where answer[j] is true if the jth query of type "query ui vi" can be rearranged into a palindrome, and false otherwise.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]
Output: [true,false]
Explanation:
"query 0 2": Path 0 → 1 → 2 gives "aac", which can be rearranged to form "aca", a palindrome. Thus, answer[0] = true.
"update 1 b": Update node 1 to 'b', now s = "abc".
"query 0 2": Path characters are "abc", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.
Thus, answer = [true, false].
Example 2:
Input: 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"]
Output: [false,false,true]
Explanation:
"query 1 2": Path 1 → 0 → 2 gives "bac", which cannot be rearranged to form a palindrome. Thus, answer[0] = false.
"update 0 b": Update node 0 to 'b', now s = "bbca".
"query 2 3": Path 2 → 0 → 3 gives "cba", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.
"update 3 a": Update node 3 to 'a', s = "bbca".
"query 1 3": Path 1 → 0 → 3 gives "bba", which can be rearranged to form "bab", a palindrome. Thus, answer[2] = true.
Thus, answer = [false, false, true].
Constraints:
1 <= n == s.length <= 5 * 10^4
edges.length == n - 1
edges[i] = [ui, vi]
0 <= ui, vi <= n - 1
s consists of lowercase English letters.
The input is generated such that edges represents a valid tree.
1 <= queries.length <= 5 * 10^4
queries[i] = "update ui c" or
queries[i] = "query ui vi"
0 <= ui, vi <= n - 1
c is a lowercase English letter.
這題簡直是惡夢OAO
這是前兩天的 Hard,
題目給我們一個無向圖 edges 還有節點字串 s、節點個數 n 跟 查詢陣列 queries。
題目要我們把這圖當樹,
根據查詢陣列計算、更新,依照順序回傳是迴文的查詢 query。
這題麻煩的地點在於壓縮更新、查詢的計算複雜度,
真的會死人。
既然無向圖就是不在意 root 在哪裡,
我們先做鄰接表、樹、還有深度表,
深度表等等算 LCA 會用到。
然後再計算快查表 bit,
這個對於更新區間差分有用。
這題的核心概念有幾個:
- 兩段區間是不是迴文,可以用 bit mask 表示,最多一個 1 ,所以最後利用二進位特性,只有一個 pilot 1 時 i & i - 1 == 0。
- bit mask 的差分表是 bit表,每個區間都會被 bit 表統管。
- 查詢 u, v 區間的時候,以樹的觀點來說路徑就是 bit mask 做 [root, u] XOR [root, v] XOR LCA,因為只有 LCA 同時經過兩次被消除,但又存在路徑內,得 XOR 回來。
解 trival 逐元素更新的關鍵是 up 快查表。
up 快查表的建構方式是 up[k][x],
從元素索引 x 出發走 k 步會到哪個索引?
接著就是利用 bit mask 管差分快查表 bit 去更新了,
我寫這題的當下是傻的,現在才看懂大概。
C++程式碼太長了,今天先不放。
計算複雜度:O((Q + N) * logN)
-> 建圖 + DFS O(N)
-> 快查表 buildLifting O(NlogN)
-> update O(logN)
-> Q次計算 LCA O(logN) + 計算 currMask O(logN)
空間複雜度:O(NlogN + Q)
-> 被 up O(NlogN) + res O(Q) 所決定,其餘都是 O(N)
Github程式碼:

