題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF593D Happy Tree Party

Problem Statement

題目簡述

給定一棵 nn 個節點的樹，每條邊有一個權值 xix_i。接著有 mm 個操作：

  1. 1 a b y：從節點 aa 走到 bb，沿途將 yy 變成 ⌊yw⌋\lfloor \frac{y}{w} \rfloor，其中 ww 是經過的邊權。求最終的 yy。
  2. 2 p c：將第 pp 條邊的權值修改為 cc（保證 cc 小於當前權值）。

Constraints

約束條件

  • 2≤n≤200,0002 \le n \le 200,000
  • 1≤m≤200,0001 \le m \le 200,000
  • 1≤xi,y≤10181 \le x_i, y \le 10^{18}
  • 修改操作只會讓邊權變小。

思路：暴力 + 併查集優化 + 數論

核心觀察

關鍵洞察：除法的快速收斂

當 yy 除以一個 ≥2\ge 2 的整數時，數值會迅速減小。最多經過 ≈60\approx 60 次除法（log⁡21018\log_2 10^{18}），yy 就會變成 00。

  1. 除法性質：真正「有效」的除法操作次數上限為 O(log⁡y)O(\log y)。
  2. 無效邊：當邊權為 11 時，除法操作 ⌊yw⌋=y\lfloor \frac{y}{w} \rfloor = y 不會改變 yy 的值。
  3. 優化方向：由於 n,mn, m 很大，暴力模擬路徑會 TLE。但真正有效的操作次數很少，時間主要消耗在「遍歷邊權為 1」的路徑上。因此，我們需要快速跳過這些無效邊。

解決方案

使用 併查集（DSU） 來維護邊權為 1 的連通塊，達到「跳過無效邊」的效果。

  • 集合定義：若節點 uu 與其父節點的邊權為 1，則將 uu 與父節點合併。
  • 代表元性質：find(u) 應指向該連通塊中深度最淺的節點，即「從 uu 往上走，連續的一段 1 邊路徑的最高點」。當我們在查詢時遇到 1 邊，利用 find 可以直接跳到這條路徑的盡頭。

操作處理

  1. 查詢 (Type 1)：

    • 類似求 LCA 的過程。維護兩個指針 a,ba, b，每次選擇 深度較大 的點往上跳。
    • 使用 find 快速跳過邊權為 1 的路徑。
    • 若當前邊權 >1>1，則執行除法 y←⌊y/w⌋y \leftarrow \lfloor y/w \rfloor，並移動到父節點。
    • 若 yy 變為 0，則後續答案必為 0，可提前結束。
    • 當 aa 和 bb 屬於同一個 DSU 集合（或相遇）時停止。

  2. 修改 (Type 2)：

    • 直接修改邊權。
    • 由於題目保證邊權只減不增，若邊權更新為 1，這條邊以後都可被跳過。
    • 理論上，當邊權更新為 1 時便可以立即呼叫 find 進行合併。
    • 然而，測試資料的分布可能使等到「查詢時才合併」的策略比「更新時就合併」更優許多。
Python 實作細節

對於 C++ 等語言，無論採用哪種策略都能 AC。但 Python 因效能限制，必須採用更優的 Lazy 策略：在查詢時遇到邊權為 1 的邊才進行向上合併，否則會 TLE。

複雜度分析

  • 時間複雜度：O((n+mlog⁡U)⋅α(n))\mathcal{O}((n + m \log U) \cdot \alpha(n))。每條邊最多被壓縮一次（O(n)O(n)），而每次查詢最多進行 log⁡U\log U 次有效除法。
  • 空間複雜度：O(n)\mathcal{O}(n)，用於存儲樹結構、邊權與併查集。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import sys
input = lambda: sys.stdin.readline().strip()
print = lambda *args, sep=' ', end='\n': sys.stdout.write(sep.join(map(str, args)) + end)

def solve():
    n, m = map(int, input().split())
    
    edges = []
    g = [[] for _ in range(n)]
    for eid in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edges.append([u, v, w])
        g[u].append((v, eid))
        g[v].append((u, eid))
    
    # DSU
    pa = list(range(n))
    def find(x):
        while pa[x] != x:
            pa[x] = pa[pa[x]]
            x = pa[x]
        return x
    
    to_fa = [(-1, -1)] * n  # (fa, eid)
    dep = [0] * n
    def dfs(u):
        # for v, eid in g[u]:
        #     if v == to_fa[u][0]:
        #         continue
        #     if edges[eid][2] == 1:
        #         pa[v] = find(u)
        #     to_fa[v] = (u, eid)
        #     dep[v] = dep[u] + 1
        #     dfs(v)
        st = [u]
        while st:
            u = st.pop()
            for v, eid in g[u]:
                if v == to_fa[u][0]:
                    continue
                if edges[eid][2] == 1:
                    pa[v] = find(u)
                to_fa[v] = (u, eid)
                dep[v] = dep[u] + 1
                st.append(v)
    dfs(0)

    ans = []
    for _ in range(m):
        op, *args = map(int, input().split())
        if op == 1:
            a, b, y = args
            a -= 1
            b -= 1
            a, b = find(a), find(b)
            while y > 0 and a != b:
                if dep[a] > dep[b]:
                    a, b = b, a
                fa, eid = to_fa[b]
                y //= edges[eid][2]
                # Python 需要在查詢時才合併，否則會 TLE
                if edges[eid][2] == 1:
                    pa[b] = find(fa)
                b = find(fa)
            ans.append(y)
        else:
            eid, c = args
            eid -= 1
            edges[eid][2] = c
            # 其他語言可以在更新時就合併
    
    print(*ans, sep='\n')

if __name__ == "__main__":
    solve()

寫在最後

PROMPT

這裡什麼都沒有。