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
Author ID 
Password 
 Register new ID

Count on the path

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


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
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.000000(s) query 1, Server time : 2024-11-02 09:51:22, Gzip enabled