1993. Operations on Tree

Operations on Tree

題目描述： 設計一個樹狀結構的鎖定系統 LockingTree。給定一棵以節點 0 為根的樹（用 parent 陣列表示），支援三種操作：

• lock(num, user)：若節點 num 未被鎖定，則由 user 鎖定。
• unlock(num, user)：若節點 num 被 user 鎖定，則解鎖。
• upgrade(num, user)：若節點 num 未被鎖定、至少有一個子孫被鎖定、且所有祖先都未被鎖定，則鎖定此節點並解鎖所有子孫。

解題思路：

1. 建構時建立子節點列表（children）以支持向下搜尋。
2. lock / unlock：直接檢查與更新鎖定狀態陣列。
3. upgrade：
   • 先檢查節點本身未被鎖定。
   • 向上遍歷所有祖先，確認沒有任何祖先被鎖定。
   • 用 DFS 向下搜尋所有子孫，收集被鎖定的子孫並解鎖。
   • 若有至少一個被鎖定的子孫，則鎖定當前節點，回傳 true。

時間複雜度：

• lock / unlock：O(1)
• upgrade：O(n) — 最壞情況需要遍歷所有祖先 O(h) + 所有子孫 O(n)。

空間複雜度：O(n) — 儲存子節點列表和鎖定狀態。

BFS 取代 DFS：在搜尋子孫時使用 BFS（佇列），邏輯相同但對寬樹更易理解。時間複雜度不變。

懶更新 + 標記傳播：類似線段樹的懶標記，在需要時才傳播解鎖操作。可以攤銷 upgrade 的成本，但實作複雜度顯著增加，且本題約束下不必要。

1. 如果允許一個節點被多個使用者同時鎖定（共享鎖），資料結構應如何修改？
2. 如何優化 upgrade 操作使其平均時間更短？（提示：維護鎖定子孫的計數）
3. 如果樹結構會動態變化（新增/刪除節點），設計需要如何調整？