---
tags: CSES題解
---

---
tags: CSES題解
---

# CSES Problem Set — Path Queries II 題解

## 題目
給定一個 $n$ 個節點的樹，每個節點依序被編號為 $1, 2, \ldots, n$。每個節點都有一個數值，目標是要執行下面兩種查詢。

1. 將節點 $s$ 的數值改成 $x$
2. 尋找節點 $a$ 到 $b$ 之間的路徑之間所有節點的最大值

### 輸入
- 第一行有兩個正整數 $n, q$ ($1 \le n, q \le 2 \cdot 10^5$)
- 第二行有 $n$ 個正整數 $v_1, v_2, \ldots, v_n$ ($1 \le v_i \le 10^9$)，代表第 $i$ 個節點的數值
- 接下來 $n-1$ 行，每行有兩個正整數 $a, b$ ($1 \le a, b \le n$)，代表節點 $a$ 和 $b$ 之間有一條邊
- 最後 $q$ 行輸入代表查詢，格式為 $1\ s\ x$ 或 $2\ a\ b$ ($1 \le s \le 10^9, 1 \le x \le n$)

### 輸出
對於每個查詢 $2$，輸出一個數字代表答案（分別以空白隔開）。

## 範例測資

Input:
5 3
2 4 1 3 3
1 2
1 3
2 4
2 5
2 3 5
1 2 2
2 3 5

Output:
4 3


## 先備知識
1. 用線段樹做動態 RMQ 問題

## 想法
這個問題的難點在於「需要動態更新，並且維護樹上任意兩點的最大值」，但我們並沒有好用的資料結構去維護樹的動態更新 RMQ 問題。

因此有個想法：「如果把樹拆成一個一個鏈，就可以用線段樹做動態 RMQ 了。

因為是分解成鏈，因此是要把所有需要的部分透過線段樹取 $\max$，最後再把所有結果取 $\max$。

但要怎麼拆才會比較好呢？如果拆的太爛，就會一直用線段樹查詢，進而使時間複雜度變得糟糕。

---

我們得用輕重鏈剖分（Heavy-Light Decomposition, 以下簡稱 HLD）的方式分解，因為 HLD 有個特別的性質是分解過後**任意兩點只會經過至多 $\log{N}$ 個鏈**，綜合上面的想法可以發現我們將得到以下的時間複雜度。

- 查詢 $1$：只需要更新其中一條鏈的值：$O(\log{N})$
- 查詢 $2$：至多跑過 $\log{N}$ 條鏈，每條鏈會用 $O(\log{N})$ 的時間做 RMQ，因此時間複雜度會是 $O(\log{\log{N}})$

這篇題解就不詳細介紹 HLD，可以參考 [本篇教學文章](https://usaco.guide/plat/hld?lang=cpp)，但更多本題實作細節可以參考下方程式碼與註解。

---

最後，這題的時間複雜度卡的比較緊，記得將程式碼做以下操作：
- 加上 `ios::sync_with_stdio(0), cin.tie(0);`
- 不使用 `long long`，僅用 `int`
- 加上 `#pragma GCC optimize("O3")`

若仍過不了，可以參考以下操作：
- 改用非遞迴式線段樹
- 使用更快的輸入優化
:::spoiler 輸入優化程式碼

// fast IO
inline char readchar(){
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}
inline int nextint(){
    int x = 0, c = readchar(), neg = false;
    while(('0' > c || c > '9') && c!='-' && c!=EOF) c = readchar();
    if(c == '-') neg = true, c = readchar();
    while('0' <= c && c <= '9') x = (x<<3) + (x<<1) + (c^'0'), c = readchar();
    if(neg) x = -x;
    return x; // returns 0 if EOF
}

// 將原本程式碼中 cin >> a >> b 改成 a = nextint(); b = nextint();

:::

## 程式

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3") // 務必打開
 
const int MAX_N = 2e5+10;
const int INF = 2e9;

int n, q;
vector<int> v(1);              // 數值陣列，(based-1)
vector<vector<int>> G(MAX_N);  // 樹
 
vector<int> sz(MAX_N);         // sz[i] = i 的子樹大小為何
vector<int> parent(MAX_N);     // parent[i] = i 的父節點為何
vector<int> dep(MAX_N);        // dep[i] = i 的深度為何，以下稱「高」為靠近根，「低」則反之
 
int now_id = 0;                // 計數器
vector<int> id(MAX_N);         // id[i] = 將樹分解後，每個節點的新編號（based-0）
vector<int> lead(MAX_N);       // lead[i] = i 目前在的重鏈中最上高是誰
 
struct Segment_Tree{
    struct Node{
        int ma = -INF;
    };
    vector<Node> arr;
 
    Segment_Tree(int _n){
        arr.resize(_n*4+10);
    }
    
    // 將兩個節點的數值合併
    Node pull(Node a, Node b){
        Node c;
        c.ma = max(a.ma, b.ma);
        return c;
    }

    // 將 [ll, rr) 的數值建在線段樹中
    void build(vector<int> &v, int idx = 0, int ll = 0, int rr = n){
        if (rr-ll==1){
            arr[idx].ma = v[ll];
            return;
        }
 
        int mid = (ll+rr)/2;
        build(v, idx*2+1, ll, mid);
        build(v, idx*2+2, mid, rr);
        arr[idx] = pull(arr[idx*2+1], arr[idx*2+2]);
    }
    
    // 將在 pos 的節點數值改成 val
    void update(int pos, int val, int idx = 0, int ll = 0, int rr = n){
        if (rr-ll==1){
            arr[idx].ma = val;
            return;
        }
 
        int mid = (ll+rr)/2;
        if (pos<mid) update(pos, val, idx*2+1, ll, mid);
        else update(pos, val, idx*2+2, mid, rr);
        arr[idx] = pull(arr[idx*2+1], arr[idx*2+2]);
        return;
    }
    
    // 查詢 [ql, qr) 的最大值
    Node query(int ql, int qr, int idx = 0, int ll = 0, int rr = n){
        if (rr<=ql || qr<=ll) return Node();
        if (ql<=ll && rr<=qr) return arr[idx];
 
        int mid = (ll+rr)/2;
        return pull(query(ql, qr, idx*2+1, ll, mid), query(ql, qr, idx*2+2, mid, rr));
    }
};
 
void dfs_sz(int now, int pre){ // now = 目前的節點, pre = now 的父節點
    sz[now]++;
    parent[now] = pre;
    dep[now] = dep[pre]+1;
 
    for (auto x : G[now]){
        if (x==pre) continue;
        dfs_sz(x, now);
        sz[now] += sz[x];
    }
    return;
}
 
void dfs_HLD(int now, int pre, int now_lead){ // now = 目前的節點, pre = now 的父節點, now_lead = 目前的鏈，誰是最高的節點
    id[now] = now_id++;
    lead[now] = now_lead;
 
    // 找到重鏈應該往哪裡走
    int ma = -INF, ma_id = -1; // ma_id = 哪個子節點的子樹大小最大, ma = ma_id 的子樹大小
    for (auto x : G[now]){
        if (x==pre) continue;
        if (sz[x]>ma){
            ma = sz[x];
            ma_id = x;
        }
    }
 
    // 如果已經沒有子節點了，就停止遞迴
    if (ma_id==-1) return;

    // 先走重鏈，now_lead 跟現在的同一個
    dfs_HLD(ma_id, now, now_lead);

    // 再走輕鏈，此時所有輕鏈自成一個重鏈，因此他們的 now_lead 都是自己
    for (auto x : G[now]){
        if (x==pre || x==ma_id) continue;
        dfs_HLD(x, now, x);
    }
    return;
}
 
int query(Segment_Tree &st, int x, int y){

    // 全部答案要取的最大值
    int ma = -INF;
 
    // 若 x 跟 y 在不同鏈上，則用類似 LCA 的感覺往上跳
    while (lead[x]!=lead[y]){

        // x 是比較低的點，也就是要往上跳的點
        if (dep[lead[x]]<dep[lead[y]]) swap(x, y);

        // 更新 ma，擷取 x 到 lead[x] 之間的最大值（因為右邊是開區間，所以 +1）
        ma = max(ma, st.query(id[lead[x]], id[x]+1).ma);

        // 跳到 lead[x] 的父節點，也就是另一條鏈上
        x = parent[lead[x]];
    }
 
    // 若 x 跟 y 在同一條鏈上，則擷取他們之間的最大值
    if (dep[x]<dep[y]) swap(x, y);
    ma = max(ma, st.query(id[y], id[x]+1).ma);
    
    return ma;
}
 
int main(){

    // setup
    ios::sync_with_stdio(0), cin.tie(0); // 務必打開
 
    // input
    cin >> n >> q;
    for (int i=1 ; i<=n ; i++){ // 記得是 based-1
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    for (int i=0 ; i<n-1 ; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
 
    // 找出每個人的子樹大小
    dfs_sz(1, 0);
 
    // 蓋出 HLD
    dfs_HLD(1, 0, 1);
 
    // 蓋線段樹
    Segment_Tree st(n);
    vector<int> p(MAX_N); // p[i] = 重新編號為 i 的節點的數值
    for (int i=1 ; i<=n ; i++){
        p[id[i]] = v[i];
    }
    st.build(p);
 
    // queries
    for (int i=0 ; i<q ; i++){
        int ty;
        cin >> ty;
 
        if (ty==1){
            int s, x;
            cin >> s >> x;
            st.update(id[s], x);

        }else if (ty==2){
            int a, b;
            cin >> a >> b;
            cout << query(st, a, b) << " ";

        }
    }
 
    return 0;
}

> 執行時間比較危險，記得壓點常數