QTREE3 - Query on a tree again!

Truy vấn trên cây

Cho một cây (đồ thị vô hướng phi chu trình) có N nút. Các nút của cây được đánh số từ 1 đến N. Ban đầu, mỗi nút đều có màu trắng.

Bạn phải thực hiện các thao tác có dạng sau:

  • 0 i: đổi màu nút thứ i (từ đen thành trắng, hoặc từ trắng thành đen)
  • 1 v: tìm chỉ số của nút đen đầu tiên trên đường đi từ nút 1 đến nút v. Nếu không tồn tại, hãy trả về -1.

Dữ liệu

  • Dòng thứ nhất gồm hai số nguyên NQ.
  • N-1 dòng sau, mỗi dòng gồm hai số nguyên a b mô tả một cạnh nối giữa nút a và nút b.
  • Q dòng sau chứa các thao tác dạng "0 i" hoặc "1 v" (1 ≤ i, v ≤ N).

Kết quả

Với mỗi thao tác dạng "1 v", in ra một số nguyên là kết quả.

Ví dụ

Dữ liệu
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9 

Kết quả
-1
8
-1
2
-1

Giới hạn

Có 12 test:

  • Trong 1/3 số test, N=5000, Q=400000.
  • Trong 1/3 số test tiếp theo, N=10000, Q=300000.
  • Trong 1/3 số test tiếp theo, N=100000, Q=100000.

Được gửi lên bởi:Fudan University Problem Setters
Ngày:2008-06-14
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon '08 - Round 6/DivA
Problem Setter: Blue Mary

hide comments
2020-10-07 12:47:03
ez
2020-06-27 13:45:35
Tham khảo:
Solution: http://megaurl.in/qMPdLCYW
Code: http://megaurl.in/TDxRX
2019-09-17 02:23:30
:)
2019-09-06 20:32:15
same ques RESULT:0 TIME: 0.00 MEM: 0k là bị s vậy mn :v..
2019-08-04 16:21:21
RESULT:0 TIME: 0.00 MEM: 0k là bị s vậy mn :v..
2018-07-29 19:09:47
Cái truy vấn cuối phải là 2 chứ nhỉ?
2018-01-05 03:43:54
1 đấm AC :>
chạy lâu v.l =))))
frostpixel aka.How 2 AC
2017-05-17 11:47:04
hạnh phúc khi AC sau 1 buổi code :v
2016-09-08 02:21:00
Heavy Light Decomposittion
2016-05-24 12:18:08
HL + IT, 100 dòng :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.