Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Truy vấn tổng trên đường đi

    Cho cây gồm nnn đỉnh, mỗi đỉnh iii mang giá trị valival_ivali​. Xử lý qqq truy vấn:

    • 1 p x: gán giá trị đỉnh ppp thành xxx.
    • 2 u v: in tổng giá trị các đỉnh trên đường đi từ uuu tới vvv (bao gồm cả hai đầu mút).

    Sử dụng phân tách cây nặng-nhẹ (Heavy-Light Decomposition) kết hợp cây phân đoạn để mỗi truy vấn chạy O(log⁡2n)O(\log^2 n)O(log2n).

    • Định dạng đầu vào:

      Dòng đầu chứa nnn và qqq. Dòng thứ hai chứa nnn số nguyên val1…valnval_1 \dots val_nval1​…valn​. n−1n-1n−1 dòng tiếp theo, mỗi dòng hai số mô tả một cạnh. qqq dòng cuối mô tả truy vấn.

    • Ràng buộc đầu vào:

      1≤n,q≤1051 \le n, q \le 10^51≤n,q≤105, ∣vali∣≤109|val_i| \le 10^9∣vali​∣≤109, ∣x∣≤109|x| \le 10^9∣x∣≤109.

    • Định dạng đầu ra:

      Với mỗi truy vấn loại 222, in tổng trên một dòng.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    12
19

    Giải thích:

    Đường đi từ 4 tới 5 đi qua 4-3-5, tổng giá trị 4+3+5=12. Sau khi đặt giá trị đỉnh 3 thành 10, tổng trở thành 4+10+5=19.

    Đang tải editor...