CSES - Path Queries | Truy vấn đường đi

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 giá trị trên đường đi từ gốc cây tới nút \(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 4
1 3 2
2 4

Sample Output

11
8

Bình luận


  • -1
    N7hoatt    4:54 p.m. 29 Tháng 8, 2023 ← đã chỉnh sửa

    Cho một cây 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ị đỉnh \(s\) thành \(x\).
    2. Tính tổng giá trị trên đường đi từ gốc đến đỉnh \(s\).

    Input

    • Dòng đầu tiên gồm hai số nguyên \(n\), \(q\): số lượng đỉnh và số lượng 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 từng đỉnh.
    • \(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh nối giữa \(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 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 v_i, x\leq 10^9\).

    Example

    Test

    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
    Note