CSES Problem Set — Path Queries 題解
===

題目
---
給一個有 $n$ 節點的有根樹。節點分別編號為 $1$ 到 $n$，其中節點 $1$ 為根。每個節點都有數值。

你的任務是處理以下兩種查詢：
1. 將節點 $s$ 的數值改為 $x$。
2. 計算從根結點到節點 $s$ 的路徑的數值總和。

### 輸入
- 第一行有兩個正整數 $n$ 與 $q$，分別代表節點與查詢數量。（$1 \le n, q \le 2 \cdot 10^5$）
- 每個節點編號為 $1$ 到 $n$。
- 第二行有 $n$ 個正整數 $v_i$，分別代表節點 $i$ 的數值。（$1 \le v_i \le 10^9$）
- 接著有 $n-1$ 行代表樹的邊。每行有兩個正整數 $a$ 與 $b$，代表節點 $a$ 與節點 $b$ 互相連結。（$1 \le a,b \le n$）
- 最後有 $q$ 行代表查詢。每個查詢是「$1$ $s$ $x$」或「$2$ $s$」兩種形式之一。（$1 \le s \le n$、$1 \le x \le 10^9$）

### 輸出
對於每個查詢 $2$，都輸出一行結果。

範例測資
---

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

Output :
11
8


想法
---
1. 如果 $v$ 的子樹中有個點 $u$ 要計算答案，則一定會走到 $v$。==（跟子樹有關，考慮樹壓平）==。
2. 若只考慮查詢，每個節點對的答案可以以下面方式求得：將每個點的價值，加在他的子樹的所有節點。==（考慮差分區間修改 / 懶標 DFS 的概念）==。
- 
3. 同時考慮更新，可以使用樹壓平 + BIT + 差分 / 線段樹區間加值查詢。

### 範例程式碼
:::spoiler {state="open"} C++ 範例

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 5e5+5;
 
int n, q;
int a, b, c;
vector<int> v;
vector<vector<int>> G(MAX_N);

// 樹壓平
int id = 1;
vector<int> L(MAX_N), R(MAX_N);
void dfs(int now, int pre = -1) {
    L[now] = id++;
    for (auto x : G[now])
        if (x != pre)
            dfs(x, now);
    R[now] = id++;
    return;
}

struct BIT {
    #define lowbit(i) (i & -i)
    int len;
    vector<int> arr;
    BIT(int n): len(n), arr(n, 0) {}
    void update(int idx, int val) {
        for (int i = idx; i < len; i += lowbit(i))
            arr[i] += val;
        return;
    }
    int query(int idx) {
        int result = 0;
        for (int i = idx; i > 0; i -= lowbit(i))
            result += arr[i];
        return result;
    }
};

int main() { 
    // input
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a;
        v.push_back(a);
    }
    for (int i = 0; i < n-1; i++) {
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // step 1: build tree flatting array
    dfs(0);

    // step 2: update BIT value
    BIT t(MAX_N);
    for (int i = 0; i < n; i++) {
        t.update(L[i], v[i]);
        t.update(R[i], -v[i]);
    }

    // step 3: queries
    for (int i = 0; i < q; i++) {
        cin >> a;
        if (a == 1) {
            cin >> b >> c;
            b--;
            t.update(L[b], c-v[b]);
            t.update(R[b], -c+v[b]);
            v[b] = c;
        } else {
            cin >> b;
            b--;
            cout << t.query(R[b]-1) << "\n";
        }
    }
}

:::

---
回 [「CSES題解集」](https://hackmd.io/MpE3CP9eQUu20n3scMF5Fw?view)