求LCA

题目描述:

给定一棵n个点以1为根的树，Q个询问[L,R]，求点L，点L+1，点L+2，...，点R的LCA。

PS：此题两个Log的做法比较显然，思考一下一个log的做法。

输入格式:

多组数据，每组数据：

第一行，一个数n（2<=n<=300,000)。

接下来n-1行，每行两个数bi 和ci，一条边的两个端点。

接下来一行是Q个询问，Q(Q<=300,000）。

接下来Q行，每行两个值表示区间的端点Li和Ri。

输出格式:

针对每组数据，输出Q个整数表示【Li,Ri】的LCA。

样例输入:

5
1 2
1 3
3 4
4 5
5
1 2
2 3
3 4
3 5
1 5

样例输出:

1
1
3
3
1

时间限制: 2000ms
空间限制: 256MB

---