CSES - Subtree Queries | Truy vấn cây con

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , haidanghutcansa , An09855
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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


  • -1
    N7hoatt    4:32 p.m. 17 Tháng 8, 2023

    Cho một cây có gốc gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1,2,3,\dots,n\) và đỉnh \(1\) là gốc của cây. Mỗi đỉnh có một giá trị.

    Hãy thực hiện \(q\) truy vấn có dạng:

    1. Thay đổi giá trị của đỉnh \(s\) thành \(x\).
    2. Tính tổng giá trị trong cây con gốc \(s\).

    Input

    • Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\) lần lượt là số đỉnh và số truy vấn. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
    • Dòng tiếp theo gồm \(n\) số nguyên \(v_1,v_2,v_3\dots,v_n\): giá trị của mỗi đỉnh \(1,2,3,\dots,n\).
    • \(n - 1\) dòng tiếp theo mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh giữa hai đỉnh \(a\) và \(b\).
    • \(q\) dòng cuối cùng biểu diễn các truy vấn. Mỗi truy vấn có dạng "1 s x" hoặc "2 s".

    Output

    • In ra kết quả cho \(q\) truy vấn loại 2.

    Constraints

    • \(1\leq n,q\leq 2 \times 10^5\).
    • \(1\leq a,b,s\leq n\).
    • \(1\leq x, v_i\leq 10^9\).

    Example

    Test

    Input 
    5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3
    Output 
    8
10
    Note
    • 1 bình luận nữa