Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOTREE - Cây

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/votree


Cho cây gồm N đỉnh, có gốc ở đỉnh 1. (N ≤ 70,000). Bạn cần trả lời Q truy vấn, mỗi truy vấn gồm 2 số u, v. Bạn cần tìm đỉnh xa gốc nhất, mà là tổ tiên của tất cả các đỉnh u, u+1, ..., v.

Input

  • Dòng 1: Số nguyên dương N và Q.
  • N-1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương u và v, thể hiện có 1 cạnh nối giữa 2 đỉnh u và v. (u ≠ v, 1 ≤ u, v ≤ N).
  • Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương u và v (1 ≤ u ≤ v ≤ N), thể hiện 1 truy vấn.

Output

Với mỗi truy vấn, in ra 1 dòng duy nhất là đáp số của truy vấn.

Giới hạn

  • Trong 30% số test, 1 ≤ N, Q ≤ 1000.
  • Trong tất cả các test, 1 ≤ N, Q ≤ 70,000.
  • Thời gian chạy: 1s. Thời gian chạy cho test ví dụ: 0.5s

Chú ý:

  • Trong thời gian thi, bài của bạn chỉ được chấm với test đề bài.
  • Nếu bài của bạn chạy đúng trên máy mình, nhưng sai khi nộp lên SPOJ, bạn có thể kiểm tra ở ideone. Chú ý khi submit lên ideone, để chế độ Secret để người khác không đọc được code của bạn.

Example

Input:
5 3
1 2
2 3
3 4
3 5
2 5
1 3
4 5

Output:
2
1
3

Được gửi lên bởi:VOJ Team
Ngày:2014-12-26
Thời gian chạy:0.5s-1s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VO 2015

hide comments
2019-09-24 11:26:32
AC là dễ
quy hoạch động + hash + hld + dfs :<<
500 dòng 30p ~~
duonght_pro_xinhgainhathemattroi_:)

Last edit: 2019-09-24 11:27:53
2019-09-05 05:41:59
facebook của mk đây nha tại nhiều bạn hỏi quá :)(()
https://www.facebook.com/dungbui.t1k28
2019-09-04 19:21:00
anh ở dưới cho em fb chứ e ko biết nhắn trên spoj anh ạ :((( huhu
Anh thật là đáng sợ quá đi :(

Last edit: 2019-09-04 19:21:27
2019-09-03 08:43:16


Last edit: 2019-09-16 16:35:53
2018-12-15 12:07:05
one hit nha :v
2018-11-15 11:24:47
cc
2018-08-05 15:12:49
de_vailon
2018-07-28 20:20:08
mất chục đấm vì log2 mà ghi log -.-
2017-12-19 04:58:20
1 đấm AC ~.~
Chạy lâu quá =)))
Vừa học LCA
frostpixel aka.How 2 AC
2017-11-25 13:36:13
1 đấm 100
range minimum query <=> lowest common ancestor và range LCA query
https://gist.github.com/quachtridat/1baa6200c92317b6d6fbf0e83bd8a488
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.