洛谷 P3379 【模闆】最近公共祖先（LCA）

剛剛學習LCA，是以刷一道LCA的闆子題。

模闆題，發現不需要RMQ+ST，倍增也可以過。

存圖用到了數組模拟連結清單。還有一個小的坑點，用C++的标準輸入輸出Cin/Cout有仨點會TLE的 （A的時候找了半天才發現又被輸入輸出坑了）

改用scanf/printf 完美AC（曾經在做poj3264就被坑過一次）

貼代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
	int n,m,root,head[maxn];
	int deep[maxn],f[maxn][25];
struct edge{
	int t;
	int next;
}e[2 * maxn];
int tot = 0; 
int add(int x,int y)//添加x->y的邊 
{
	e[++tot].t = y;
	e[tot].next = head[x];
	head[x] = tot;
}
int dfs(int r,int dp,int father){
	deep[r] = dp;
		f[r][0] = father;
		for(int i=1;(1<<i)<=deep[r];i++)
	 f[r][i]=f[f[r][i-1]][i-1]; 
	for(int i=head[r];i;i=e[i].next)
		if(e[i].t != father)	
			dfs(e[i].t,dp+1,r);	
} 
int LCA(int x,int y)
{

	if(deep[x] < deep[y]) swap(x,y);
	if(deep[x] != deep[y])
		for(int i=log2(deep[x]-deep[y])+1;i>=0;i--)
		{
			if(deep[f[x][i]]>=deep[y]){
				x = f[x][i];
				if(deep[x]==deep[y])
					break;
			}			
		}
	if(x!=y)
	{
		for(int i=log2(deep[x])+1;i>=0;i--)	
			if(f[x][i] != f[y][i])
			{
				x = f[x][i];
				y = f[y][i];
			} 
		x = f[x][0];
	}
	return x;
}
int main()
{
	scanf("%d%d%d",&n,&m,&root);
		int v1,v2;
		for(int i=0;i<n-1;i++)
		{
			scanf("%d%d",&v1,&v2);
			add(v1,v2);
			add(v2,v1);
		}
		dfs(root,1,0);
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&v1,&v2);
			printf("%d\n",LCA(v1,v2));
		}	
	
}