 2017-09-22 01:35

# Count on the path

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

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答