Quản lý công ty

View as PDF
Submit solution
Points: 1.05 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Tranhu Thái Huy
Problem types
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    pppssslc  commented on July 8, 2025, 9:42 a.m.

    Một cách tiếp cận khác cho bài toán

    BIT + Euler tour + TKNP

    Euler tour:

    • Lưu các ~in[u]~ theo từng độ sâu.
    • Mỗi độ sâu sẽ được xắp sếp theo thứ tự tăng dần.

    TKNP:

    • Gọi ~st~ và ~en~ là thời gian nút của con bậc ~k~ của ~u~ có ~in~ nhỏ nhất và lớn nhất.
    • Hay có thể nói là tìm phần tử đầu tiên ~\ge in[u]~ và phần tử cuối cùng ~\le out[u]~.
    • Ta sẽ TKNP trong độ sâu ~d[u] + k~ để tìm ~st~ và ~en~.

    BIT:

    • Tại mỗi độ sâu ta sẽ dùng 1 BIT để cập nhật và truy vấn.

    Lưu ý:

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

    ĐPT: ~O\left(n \log_2 n\right)~


  • 0
    pppssslc  commented on July 5, 2025, 3:04 p.m. ← edit 9

    My solve

    BIT + BFS + Binary lifting/Euler tour + TKNP:

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

    • Ta Bfs đánh dấu thời điểm gặp các nút để dễ dàng cập nhật và truy xuất theo độ sâu.
    • Gọi ~d[u], mi[u], ma[u]~ là độ sâu của ~u~, thời gian sớm nhất và muộn nhất của nút có độ sâu là ~u~.

    Binary lifting + TKNP:

    • Gọi nút con bậc ~k~ của ~u~ có thời gian lớn nhất là ~st~ và ~en~.
    • Sử dụng tìm kiếm nhị phân để tìm ~st~ và ~en~:
    • Vì ta BFS để đánh dấu thời gian nên các nút con có cùng độ sâu sẽ có thời gian liên tiếp nhau và tăng dần.
    • Ta sẽ TKNP trong khoảng từ ~mi[d[u] + k]~ tới ~ma[d[u] + k]~.
    • Kiểm tra ~v~ có là con bậc ~k~ của ~u~ hay không:
    • C1: Binary lifting:

    Dùng binary lifting để kiểm tra cha bậc ~k~ của ~v~ có là ~u~ hay không.

    • C2: Euler tour:

    Để ~v~ là con của ~u~ thì ~in[u] \le in[v] \le out[v]~.

    BIT:

    Sử dụng BIT kết hợp với Different array để 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\left(n \log^2 n\right)~ hoặc ~O\left(n \log_2 n\right)~