• problem link
  • 有\(N\)個點，每個點有權值，一開始點都不相連，有\(Q\)個操作，強制在線，分兩種：
    1. 把 \(X\) 跟 \(Y\) 連一條無向邊。如果 \(X\) 和 \(Y\) 本身已經直接相連或間接相連，則忽略此操作。
    2. 查詢 \(X\) 到 \(Y\) 的路徑上權值 \( \le K\) 的點的數量。

  • 資料範圍：多測資，沒講幾筆，\(N \le 5 \times 10^4, Q \le 10^5\)，權值範圍不重要（？），反正太大的話可以離散化

  • 根據規則會發現建出來的是一個森林，連通性的檢查可以用併查集做。
    當\(X,Y\)連通時會在一顆樹上，隨意定根後詢問可以拆成\(X\)到根的詢問，\(Y\)到根的詢問，\(LCA(X,Y)\)到根的詢問， 就變得跟陣列版的區間第 \(K\) 小一樣可用持久化的值域線段樹做。
  • 加邊時要把兩顆樹上的資料結構合併，有點麻煩，但用啟發式合併的思想把小的併到大的，每個點只會被合併 \(O(\log N)\) 次，只要能支援新增一個點這個操作就會是好的。
  • 持久化線段樹就直接從親節點的版本插入生成一個新版本。
  • LCA 的話常見的做法好像只有倍增法能往下長一個點。（link-cut tree 什麼的就算惹）
  • Time Complexity: \(O(N \log^2 N + Q \log N)\)
  • Space Complexity: \(O(N \log^2 N)\) （寫垃圾回收的話可以壓到 \(O(N \log N)\)，可是我懶（？））
  • 這題一堆資料結構耶，苦功題（？
  • 覺得這次 LCA 寫的特別乾淨，之前倍增法 LCA 都亂寫，就貼上來惹。