USACO 2019 - Dec - Gold - Milk Visits

Xem dạng PDF

Gửi bài giải

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

Người đăng:
Nguồn bài:
http://www.usaco.org/index.php?page=viewproblem2&cpid=970
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nông dân John đang định xây ~N~ trang trại được nối bởi ~N - 1~ con đường, tạo thành một đồ thị cây (mọi trang trại tới được nhau, và không tồn tại chu trình). Trang trại ~i~ có một loại bò là ~T_{i}~.

Nông dân John có ~M~ người bạn thường đến thăm anh ấy. Trong chuyến thăm của người bạn thứ ~i~, nông dân John sẽ cùng bạn mình đi trên các con đường từ trang trại ~A_{i}~ đến trang trại ~B_{i}~ (có thể ~A_{i} = B_{i}~). Hơn nữa, họ có thể uống sữa của bất kì con bò nằm trên các trang trại dọc đường đi từ trang trại ~A_{i}~ đến trang trại ~B_{i}~. Tuy nhiên, bạn của nông dân John chỉ thích uống sữa từ một loại bò nhất định. Các bạn của nông dân John sẽ chỉ được thỏa mãn nếu như họ có thể uống sữa từ loại bò họ thích.

Hãy xác định liệu bạn của John có được thỏa mãn sau chuyến thăm.

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~N~, ~M~ ~(1 \le N, M \le 10^5)~.

  • Dòng thứ hai chứa ~N~ số nguyên ~T_{1},T_{2},...,T_{N}~ là loại bò của mỗi trang trại ~(1 \le T_{i} \le N)~.

  • ~N - 1~ dòng tiếp theo chứa 2 số nguyên ~X~ và ~Y~ phân biệt ~(1 \le X, Y \le N)~ thể hiện tồn tại 1 con đường nối trang trại ~X~ và ~Y~.

  • ~M~ dòng tiếp theo, dòng thứ ~i~ chứa các số nguyên ~A_{i}, B_{i}~ và ~C_{i}~. Trong đó ~A_{i}~ và ~B_{i}~ là hai đầu chuyến thăm của người bạn thứ ~i~, ~C_{i}~ là loại bò mà người bạn thứ ~i~ thích ~(1 \le A_{i}, B_{i}, C_{i} \le N)~.

Output

  • In ra xâu nhị phân có độ dài ~M~. Kí tự thứ ~i~ của xâu là ~1~ nếu người bạn thứ ~i~ được thỏa mãn, và ~0~ nếu ngược lại.

Sample Input 1

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

Sample Output 1

10110

Sample Input 2

6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4

Sample Output 2

0110

Giới hạn

  • Test 1-2 chính là test ví dụ.
  • Test 3 có ~N \le 10^3, M \le 2*10^3~.
  • Các tests 4-7 có ~C_{i} \le 10~.
  • Các test còn lại có giới hạn gốc.

Bình luận

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



  • 1
    dragon3012009  đã bình luận lúc 21, Tháng 4, 2025, 17:21 sửa 7

    Theo một gợi ý của tiền bối nào đó Yugi Hacker, mình đã AC bài này ✍️(◔◡◔)

    Có thể cho rằng đây là một bài hld tìm truy vấn đường đi

    Nhưng làm thế nào để quản lí màu trên cây theo từng truy vấn ?

    Tác giả cho truy vấn từng màu một dễ thấy ta có thể xử lí offline , nhưng xử lí như nào ?

    Nhận thấy mỗi truy vấn sẽ liên quan đến một màu , ta có thể sort theo màu để update lên cây segmentree trong hld và sort luôn màu các nút theo thứ tự tăng dần

    Việc quản lí thự tự các màu của nốt có thể cho vào multiset để cho dễ code

    Mỗi khi đến màu hiện tại , ta sẽ xoá các mau không liên quan trước đó đi bằng cách lưu các truy vấn đã update vào seg cho vào stack

    Việc còn lại là query trên cây từ u đến v như mọi bài hld để tìm xem có cạnh nào đang có giá trị không

    Code AC : Code của tui


  • 0
    sitingfake  đã bình luận lúc 5, Tháng 2, 2025, 3:50

    orzz


  • -10
    JELLY1010  đã bình luận lúc 1, Tháng 10, 2023, 12:55 chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.