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.

hide comments
magolor: 2017-05-11 13:29:20

Notice that "first" in query means the one with min depth.

amandal799: 2017-03-26 19:15:13

100 in second go !! simple HLD

yousiki: 2017-01-23 03:17:37

Why I got 100 instead of AC?

ankesh007: 2016-11-29 17:13:00

what does 41.67 mean?

joney_000: 2016-01-11 11:04:21

how to know how many file gives WA or TLE since score is zero for both case.

hippie: 2015-12-11 11:02:03

easy peasy :P straightforward HLD should pass

wohenshuai: 2015-11-28 01:32:59

what's means "0",My solution "a+b problem" got ac..

Luis Manuel Díaz Barón: 2015-04-23 15:16:29

100 points on the first attempt

Gary Ye: 2014-07-05 13:57:50

Wow, cin + cout with ios::sync_with_stdio(false) can get you TLE. I've debugged a 100pt solution for like > 1 hour just because of this. Guys use printf / scanf.

圣龙族骑士: 2014-06-29 11:19:40

爆栈


Added by:Fudan University Problem Setters
Date:2008-06-14
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:VNOI Marathon '08 - Round 6/DivA
Problem Setter: Blue Mary