vj Innumerable Ancestors 图

Innumerable Ancestors

题目链接

题意

给出一棵树（1为根）、有m次询问；每次询问给出两个节点集合、从这每个集合中挑出一个节点（可能相同）、让求这两个节点的lca最深是多少。
怎么做？
lca很好求，倍增，
但是节点怎么挑？
这里很巧妙？ 或许是我见识短
求出这棵树的dfs序 然后把第一个集合里的节点按照dfs序排序，然后就可以枚举第二个集合的节点二分第一个集合找出离这个节点最近的节点，要么dfs序比当前节点相等、大要么小、就这两个节点为什么是两个？不是三个吗？
因为相等的话就不用判断大或小了，
这个思路反正我是想不出来，，，害~

代码：

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e5+5;
vector<int> vv[maxn];
int fa[maxn][35];
int p[maxn];
int dep[maxn];
int pos;
void dfs(int x,int fat,int dp)
{
   
	p[x] = ++ pos;
	fa[x][0] = fat;
	dep[x] = dp;
	for (int i = 0; i < vv[x].size(); i ++ )
	{
   
		int v = vv[x][i];
		if(v == fat)
		continue;
		dfs(v,x,dp+1);
	}
}

void init(int n)
{
   
	for (int i = 1; i <= 30; i ++ )
	{
   
		for (int j = 1; j <= n; j ++ )
		{
   
			fa[j][i] = fa[fa[j][i-1]][i-1]; 
		}
	}
}
int lca(int x,int y)
{
   
	int xx = dep[x];
	int yy = dep[y];
	if(xx < yy)
	{
   
		swap(xx,yy);
		swap(x,y);
	}
		
	for (int i = 30; i >= 0; i -- )
	{
   
		if(dep[fa[x][i]] >= dep[y])
		{
   
			x = fa[x][i];
		}
	}
	for (int i = 30; i >= 0; i -- )
	{
   
		if(fa[x][i] != fa[y][i])
		{
   
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	if(x == y)
		return x;
	return fa[x][0];
}

vector<int> va,vb;
bool cmp(int a,int b)
{
   
	return p[a] < p[b];
}
void csh(int n)
{
   
	for (int i = 0; i <= n; i ++ )
	{
   
		vv[i].clear();
		dep[i] = 0;
		pos = 0;
		
	}
}

int main()
{
   
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
   
		csh(n);
		for (int i = 1; i < n; i ++ )
		{
   
			int x,y;
			scanf("%d%d",&x,&y);
			vv[x].push_back(y);
			vv[y].push_back(x);
		}
		dfs(1,0,1);
		init(n);
// for (int i = 1; i <= n; i ++ )
// {
   
// printf("%d ",p[i]);
// }
// printf("\n");
		while(m -- )
		{
   
			va.clear();
			vb.clear();
			int s1;
			scanf("%d",&s1);
			for (int i = 1; i <= s1; i ++ )
			{
   
				int x;
				scanf("%d",&x);
				va.push_back(x);
			}
			scanf("%d",&s1);
			for (int i = 1; i <= s1; i ++ )
			{
   
				int x;
				scanf("%d",&x);
				vb.push_back(x);
			}
			sort(va.begin(),va.end(),cmp);
			int ans = 0;
			for (int i = 0; i < s1; i ++ )
			{
   
				int x = lower_bound(va.begin(),va.end(),vb[i],cmp) - va.begin();
				if(x < va.size())
				{
   
					int y = lca(va[x],vb[i]);
	// printf("%d\n",y);
					ans = max(ans,dep[y]);
				}
				if(x > 0)
				{
   
					int y = lca(va[x - 1],vb[i]);
	// printf("%d\n",y);
					ans = max(ans,dep[y]);
				}
			}
			printf("%d\n",ans);
		}
	}
	
 }