Truy Vấn Cây Con

Xem dạng PDF
Gửi bài giải
Điểm: 0,20 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số ~1,2,... ,n~ và nút ~1~ là gốc của cây. Mỗi nút có một giá trị.

Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

  • ~1.~ thay đổi giá trị của nút ~s~ thành ~x~
  • ~2.~ tính tổng các giá trị trong cây con gốc ~s~

Input

  • Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~q:~ số lượng nút và truy vấn. Các nút được đánh số ~1,2,... ,n.~
  • Dòng tiếp theo có ~n~ số nguyên ~v_1,v_2,... ,v_n:~ giá trị của mỗi nút.
  • Sau đó, có ~n-1~ dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên ~a~ và ~b:~ có một cạnh nối hai nút ~a~ và ~b~.
  • Cuối cùng, có ~q~ các dòng mô tả các truy vấn. Mỗi truy vấn có dạng "~1~ ~s~ ~x~" hoặc "~2~ ~s~".

Output

  • In câu trả lời cho mỗi truy vấn loại ~2~.

Constraints

  • ~1 ≤ n, q ≤ 2⋅10^5~
  • ~1 ≤ a, b, s ≤ n~
  • ~1 ≤ v_i, x ≤ 10^9~

Example

Sample Input

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3

Sample Output

8
10

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    HaDat_Python  đã bình luận lúc 4, Tháng 1, 2026, 9:34

    include <bits/stdc++.h>

    using namespace std;

    const int MAXN = 200000 + 5;

    int n, q; long long a[MAXN]; vector<int> adj[MAXN]; int tin[MAXN], tout[MAXN], euler[2 * MAXN], timer = 0;

    // Fenwick Tree long long bit[MAXN];

    void update(int i, long long v) { for (; i <= n; i += i & -i) bit[i] += v; }

    long long query(int i) { long long s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }

    void dfs(int u, int p) { tin[u] = ++timer; euler[timer] = u; for (int v : adj[u]) if (v != p) dfs(v, u); tout[u] = timer; }

    int main() { ios::syncwithstdio(false); cin.tie(nullptr);

    cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];

for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
dfs(1, 0);
vector&lt;long long> val(n + 1);
for (int i = 1; i <= n; i++) {
    val[tin[i]] = a[i];
    update(tin[i], a[i]);
}
while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
        int u;
        long long x;
        cin >> u >> x;
        long long diff = x - val[tin[u]];
        val[tin[u]] = x;
        update(tin[u], diff);
    } else {
        int u;
        cin >> u;
        cout << query(tout[u]) - query(tin[u] - 1) << endl;
    }
}

return 0;

    }