3841. Palindromic Path Queries in a Tree 解題紀錄

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程式碼:
愛心
79
留言
encourage first comment
有些話想說嗎 快分享出來彼此交流吧!
留言……