F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Count on the path

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2334    Accepted Submission(s): 505

Problem Description
bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n.

Let f(a,b) be the minimum of vertices not on the path between vertices a and b.

There are q queries (ui,vi) for the value of f(ui,vi). Help bobo answer them.

Input
The input consists of several tests. For each tests:

The first line contains 2 integers n,q (4≤n≤106,1≤q≤106). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following q lines contains 2 integer u′i,v′i (1≤ui,vi≤n).

The queries are encrypted in the following manner.

u1=u′1,v1=v′1.
For i≥2, ui=u′i⊕f(ui - 1,vi - 1),vi=v′i⊕f(ui-1,vi-1).

Note ⊕ denotes bitwise exclusive-or.

It is guaranteed that f(a,b) is defined for all a,b.

The task contains huge inputs. scanf in g++ is considered too slow to get accepted. You may (1) submit the solution in c++; or (2) use hand-written input utilities.

Output
For each tests:

For each queries, a single number denotes the value.

Sample Input
4 1
1 2
1 3
1 4
2 3
5 2
1 2
1 3
2 4
2 5
1 2
7 6

Sample Output
4
3
1

Author
Xiaoxu Guo (ftiasch)

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.001000(s) query 1, Server time : 2024-08-14 18:17:24, Gzip enabled Administration