Quản lý công ty

Xem dạng PDF

Gửi bài giải

Điểm: 1,05 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Tranhu Thái Huy
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bờm hiện đang điều hành một công ty có đến ~N~ người ~(N \le 100000)~. Các nhân viên được đánh số từ ~1~ đến ~N~ (trong đó Bờm được đánh số ~1)~. Để dễ quản lý, mỗi người chỉ có duy nhất một giám sát trực tiếp (trừ Bờm -- giám đốc của công ty), nhưng một người lại có thể có nhiều nhân viên trực tiếp.

Đối với một người bất kì, nhân viên cấp ~1~ là nhân viên trực tiếp; và nhân viên cấp ~K~ ~(K > 1)~ là tất cả nhân viên cấp ~1~ của nhân viên cấp ~(K - 1)~.

Để tăng cường hiệu quả cũng như sự hợp tác và đoàn kết trong công ty, Bờm cho phép mỗi người có thể cùng lúc thưởng (phạt) cho tất cả các nhân cấp ~k~ (k ~>~ 0) của mình.

Do số lượng nhân viên quá đông, nên việc quản lý thưởng ~-~ phạt là một việc không dễ dàng.

Input

  • Dòng đầu tiên chứ số ~N~.

  • ~N - 1~ dòng tiếp theo là các cặp số ~(u v)~ thể hiện ~u~ là giám sát trực tiếp của ~v~.

  • Dòng tiếp theo chứa số yêu cầu - ~M~ ~(M \le 500000)~.

  • ~M~ dòng tiếp theo là các yêu cầu có dạng:

    • ~1~ ~u~ ~k~ ~e~: tăng lượng tiền thưởng của tất cả các nhân viên cấp ~k~ của ~u~ lên ~e~ đồng ~(|e| \le 2000)~.
    • ~2~ ~u~: nhân viên ~u~ muốn biết số tiền thưởng của mình hiện tại.

Output

  • In ra kết quả tương ứng đối với mỗi yêu cầu ~2~.

Sample Input

6
1 2
1 3
2 4
3 5
3 6
6
2 6
1 1 2 1000
1 2 1 100
1 3 1 -100
2 4
2 5

Sample Output

0
1100
900

Bình luận

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



  • 0
    pppssslc  đã bình luận lúc 5, Tháng 7, 2025, 15:04

    My solve

    • Ta coi công ty này là 1 cây.
    • BIT + BFS + Binary lifting + TKNP + Different array:

    • BFS(lai một chút euler tour):

      • Ta Bfs đánh dấu thời gian gặp các nút để dễ dàng cập nhật và truy xuất theo độ sâu.
    • Binary lifting + TKNP:

      • Sử dụng tìm kiếm nhị phân để tìm nút con bậc ~k~ của ~u~ có thời gian sớm nhất và muộn nhất.
    • Different array + BIT:

    • Gọi nút con bậc ~k~ của ~u~ có thời gian sớm nhất và muộn nhất lần lượt là ~st~ và ~en~.
    • Sử dụng BIT để cập nhật các nút có thời gian trong khoảng từ ~st~ tới ~en~ và truy xuất.
    • LƯU Ý:

    Xử lí trường hợp đặc biệt là không tồn tại con bậc ~k~ của ~u~.

    ĐPT : ~O(n × (log_2n)^2)~