倍增法

祖孙询问
Description
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对
节点的编号x和y，询问x与y的祖孙关系。

Input Format
输入第一行包括一个整数n表示节点个数。
接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是−1，那么a就是树的根。
第n+2行是一个整数m表示询问个数。
接下来m行，每行两个正整数x和y。

Output Format
对于每一个询问，输出1:如果x是y的祖先，输出2:如果y是x的祖先，否则输出0。

Sample Input
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
Sample Output
1
0
0
0
2

代码：

#include
using namespace std;
const int N=40220,M=N*2;
const int INF=0x3f3f3f3f;
/*
最近公共祖先：倍增 
*/

int n,m;
int h[N],e[N],ne[N],idx;
int depth[N],fa[N][16];
int q[N];

void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(int root){//预处理 
	memset(depth,0x3d,sizeof depth);
	depth[0]=0,depth[root]=1;
	queue<int> q;
	q.push(root);
	
	while(q.size()){
		int t=q.front();
		q.pop();
		
		for(int i=h[t];~i;i=ne[i]){
			int j=e[i];
			if(depth[j]>depth[t]+1){
				depth[j]=depth[t]+1;//标记节点深度
				q.push(j);
				fa[j][0]=t;//标记父节点
				for(int k=1;k<=15;k++)//标记2^k步的祖宗 
					fa[j][k]=fa[fa[j][k-1]][k-1];
			}
		}
	}
}

int lca(int a,int b){
	if(depth[a]<depth[b]) swap(a,b);
	for(int k=15;k>=0;k--)//让a和b到同一层去(二进制拼凑法) 
		if(depth[fa[a][k]]>=depth[b])
		a=fa[a][k];
	if(a==b) return a;//b是a的祖宗 
	
	for(int k=15;k>=0;k--)
		if(fa[a][k]!=fa[b][k]){//搜索到最近公共祖先的下一层 
			a=fa[a][k];
			b=fa[b][k];
		}
	return fa[a][0];
}

int main()
{
	cin>>n;
	int root=0;
	memset(h,-1,sizeof h);
	
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		if(b==-1) root=a;
		else add(a,b),add(b,a);
	}
	
	bfs(root);
	
	cin>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		int p=lca(a,b);
		if(p==a) puts("1");
		else if (p==b) puts("2");
		else puts("0");
	}
	 return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

Tarjan线性

Tarjan 的 LCA 算法

zip 0星 超过10%的资源 5KB

下载

给出 n 个点的一棵树，多次询问两点之间的最短距离。

注意：

边是无向的。
所有节点的编号是 1,2,…,n。
输入格式
第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；

下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；

再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。

树中结点编号从 1 到 n。

输出格式
共 m 行，对于每次询问，输出一行询问结果。

数据范围
2≤n≤104,
1≤m≤2×104,
0 1≤x,y≤n
输入样例1：
2 2
1 2 100
1 2
2 1
输出样例1：
100
100

代码

#include
using namespace std;
const int N=40220,M=N*2;
const int INF=0x3f3f3f3f;

typedef pair<int,int> PII;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int p[N],dist[N],st[N];
int res[N];
vector<PII> query[N];//存的查询的另外一个点和编号 

void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dfs(int u,int fa){
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa) continue;
		dist[j]=dist[u]+w[i];
		dfs(j,u);
	} 
}

int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

void tarjan(int u){
	st[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(!st[j]){
			tarjan(j);
			p[j]=u;
		}
	}
	
	for(auto it:query[u]){
		int y=it.first,id=it.second;
		if(st[y]==2){
			int anc=find(y);
			res[id]=dist[u]+dist[y]-2*dist[anc];
		}
		
	}
	st[u]=2;
}


int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;i++){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c),add(b,a,c);
	}
	
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		if(a!=b){
			query[a].push_back({b,i});
			query[b].push_back({a,i});
		}
	}
	
	for(int i=1;i<=n;i++) p[i]=i;
	
	dfs(1,-1);
	tarjan(1);
	
	for(int i=0;i<m;i++) cout<<res[i]<<endl;
	 return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

全排列函数

do
    {
        printf("%d %d %d\n",s[0],s[1],s[2]);
    }
    while(next_permutation(s,s+3));
1
2
3
4
5