Few people know, but a long time ago a developed state existed on Mars. It consisted of n cities, numbered by integers from 1 to n, the capital had the number 1. Some pairs of cities were connected by a road. The residents of the state were very prudent, therefore, between any two cities, there was exactly one path (possibly consisting of several roads).
Due to the fact that the state was developed, its residents loved traveling. Tourist route on Mars was described by two numbers L and R. This meant that the tourist started the route in the city L, then went to the city L + 1 (without going into the cities, that did not lie on the path between L and L + 1), then went to the city L + 2, and so on. The last city on the route was the city R. A city that was the closest to the capital among all cities visited on this route (if to count a distance between the cities by the roads) was considered the main attraction of the route.
Knowing the map of the Martian state and all the tourist routes, find for each route its main attraction.

Input

The first line contains an integer n that is the number of cities (1 ≤ n ≤ 2 · 105).
The following n − 1 lines describe the roads. Each road is described by two numbers of cities that are connected by it (1 ≤  v i,  u i ≤  n; v i ≠  u i).
The ( n + 1)-th line contains an integer q that is the number of tourist routes (0 ≤ q ≤ 10 6).
Then q lines describe the routes themselves. Each route is described by a pair of integers L i, R i (1 ≤ L i ≤ R i ≤ n).

Output

Output q integers, one per line — for each route the number of its main attraction. These numbers should be output in the same order in which the respective routes were described.

Example

input output 
7

1 2

1 3

2 4

2 5

2 6

3 7

3

4 6

3 4

5 7

2

1

1

7

1 3

3 5

5 6

7 5

1 4

2 4

3

4 5

5 6

6 7

1

5

5

Notes

This problem has a big input and output data size and a strict Time Limit. If you write your solution in C++ we recommend you to use Visual C++ 2013 compiler.

题意就不描述了，是个水题，预处理出i和i+1的lca，然后询问的时候跑线段树就行，这里线段树用到了寻找区间中最小的点的位置，存一下。

懒得改非递归，要手动开栈。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 200010

int n,m;

int v[N<<1],__next[N<<1],first[N],e;

void AddEdge(int U,int V)

{

    v[++e]=V;

    __next[e]=first[U];

    first[U]=e;

}

int fa[N],dep[N],top[N],son[N],siz[N],tot;

void dfs(int U)

{

    siz[U]=1;

    for(int i=first[U];i;i=__next[i])

      if(v[i]!=fa[U])

        {

          fa[v[i]]=U;

          dep[v[i]]=dep[U]+1;

          dfs(v[i]);

          siz[U]+=siz[v[i]];

          if(siz[v[i]]>siz[son[U]])

            son[U]=v[i];

        }

}

void df2(int U)

{

    if(son[U])

      {

        top[son[U]]=top[U];

        df2(son[U]);

      }

    for(int i=first[U];i;i=__next[i])

      if(v[i]!=fa[U]&&v[i]!=son[U])

        {

          top[v[i]]=v[i];

          df2(v[i]);

        }

}

int lca(int U,int V)

{

    while(top[U]!=top[V])

      {

        if(dep[top[U]]<dep[top[V]])

          swap(U,V);

        U=fa[top[U]];

      }

    if(dep[U]>dep[V])

      swap(U,V);

    return U;

}

int minv[N<<2];

void update(int p,int v,int rt,int l,int r)

{

	if(l==r)

	  {

	  	minv[rt]=v;

	  	return;

	  }

	int m=(l+r>>1);

	if(p<=m) update(p,v,rt<<1,l,m);

	else update(p,v,rt<<1|1,m+1,r);

	minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);

}

int lcas[N];

int query(int ql,int qr,int rt,int l,int r)

{

	if(ql<=l&&r<=qr) return minv[rt];

	int m=(l+r>>1),res=2147483647;

	if(ql<=m) res=min(res,query(ql,qr,rt<<1,l,m));

    if(m<qr) res=min(res,query(ql,qr,rt<<1|1,m+1,r));

    return res;

}

int Find2(int v,int rt,int l,int r)

{

	if(l==r) return l;

	int m=(l+r>>1);

	if(minv[rt<<1]==v) return Find2(v,rt<<1,l,m);

	else return Find2(v,rt<<1|1,m+1,r);

}

int Findp(int ql,int qr,int v,int rt,int l,int r)

{

	if(ql<=l&&r<=qr)

	  {

	  	if(minv[rt]==v)

	  	  return Find2(v,rt,l,r);

	  	return -1;

	  }

	int m=(l+r>>1);

	if(ql<=m)

	  {

	  	int tmp=Findp(ql,qr,v,rt<<1,l,m);

		if(tmp!=-1) return tmp;

	  }

	return Findp(ql,qr,v,rt<<1|1,m+1,r);

}

int main()

{

//	freopen("j.in","r",stdin);

	int x,y;

	scanf("%d",&n);

	for(int i=1;i<n;++i)

      {

        scanf("%d%d",&x,&y);

        AddEdge(x,y);

        AddEdge(y,x);

      }

    top[1]=1;

    dfs(1);

    df2(1);

	for(int i=1;i<n;++i)

	  {

	  	lcas[i]=lca(i,i+1);

	  	update(i,dep[lcas[i]],1,1,n-1);

	  }

	scanf("%d",&m);

	for(int i=1;i<=m;++i)

	  {

	  	scanf("%d%d",&x,&y);

	  	if(x==y)

		  printf("%d\n",x);

		else

	  	  printf("%d\n",lcas[Findp(x,y-1,query(x,y-1,1,1,n-1),1,1,n-1)]);

	  }

	return 0;

}

最新文章

  1. Linux平台 Oracle 11gR2 RAC安装Part2：GI安装
  2. Hive中的排序和分组（对map和reduce的影响，值得一看！）
  3. Cocos2d-x 3.2 学习笔记（二）创建自定义项目
  4. 由 excel 转换为 markdown，及收获
  5. ucenter 整合外部网站，实现登录等操作
  6. Lucas定理学习小记
  7. Clone PDB from same CDB
  8. 关于Asp.Net Forms身份认证
  9. 关于echarts的使用----模块化单文件引入（推荐） 与标签式单文件引入
  10. FineUI
  11. Android:AysncTask异步加载
  12. 使用（Drawable）资源——StateListDrawable资源
  13. thinkphp3.2.3 版本使用redis缓存添加认证
  14. Linux下pecl命令无法执行的解决
  15. ES6(二） Destructuring-变量的解构赋值
  16. Windows 10 Update
  17. 通过Redis、Memcache的 incr 原子操作防刷机制的使用差别
  18. linux中的标准输出和输入
  19. resize 按钮不会被伪元素遮盖
  20. 编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串。 但是要保证汉字不被截半个，如“我ABC”4，应该截为“我AB”，输入“我ABC汉DEF”，6，应该输出为“我ABC”而不是“我ABC+汉的半个”。

热门文章

  1. [poj 2796]单调栈
  2. JAVA多线程---好的博客资源收集
  3. Spring学习--xml 中 Bean 的自动装配
  4. HDU 1798 Tell me the area （数学）
  5. mongoDB的简单使用
  6. GridPanel 带头和锁定列共存
  7. python基础===python内置函数大全
  8. springmvc对于前台date类型注意点
  9. Android系统是一个基于BInder通信的C/S架构
  10. DRF的异常处理