FZYZOJ 1630(LCA)

FJYZOJ 1630
把这个依赖关系转化为一个树,询问就是求两个点$(a,b)$的$LCA$,如果$LCA=a$,则技能A学完之后才有可能学技能B。如果$LCA=b$,则技能B学完之后才有可能学技能A。否则是其他情况。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 40000 + 5, logs = 20;
int n, dep[MAXN], pre[MAXN][logs + 1], rt;
vector<int> G[MAXN];
void dfs(int u, int pa) {
dep[u] = dep[pa] + 1, pre[u][0] = pa;
for (int i=1;i<=logs;i++) pre[u][i] = pre[pre[u][i-1]][i-1];
for (int i=0;i<G[u].size();i++) {
int v = G[u][i];
dfs(v, u);
}
}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i=logs;i>=0;i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (int i=logs;i>=0;i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
void clean() {
for (int i=0;i<=n;i++) {
G[i].clear();
dep[i] = 0;
for (int j=0;j<=logs;j++) pre[i][j] = 0;
}
rt = 0;
}
void solve() {
clean();
for (int i=1;i<=n;i++) {
int s1, s2;
scanf("%d%d", &s1, &s2);
if (s2 == -1) rt = s1; else G[s2].push_back(s1);
}
dfs(rt, 0);
int Q; scanf("%d", &Q);
for (int i=1;i<=Q;i++) {
int a, b;
scanf("%d%d", &a, &b);
int lca = LCA(a, b);
if (lca == a) printf("1\n"); else if (lca == b) printf("2\n"); else printf("0\n");
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
#endif
scanf("%d", &n), solve();
fclose(stdin); fclose(stdout);
return 0;
}

题目描述

+Q很喜欢学新的东西,最近她报了一个技能培训班,她可以学习很多很多新的技能。

学习技能的规则是这样的,欲学习技能AA,必须先学习技能AA的先决技能。比如说BB是AA的先决技能,那么欲学技能AA,比先学会技能BB。现在+Q知道一些技能之间的关系,她想知道另一些技能间的关系。

每个技能最多有一个先决技能。

输入格式

输入第一行包含一个整数NN,表示技能的总数。

接下来NN行每行两个技能编号S1S1和S2S2,表示S1S1的先决技能为S2S2。如果S2S2为−1−1则表示S1S1为基础技能,可以直接学。

接下来一行为一个整数QQ,表示询问个数,最后QQ行每行用两个不同的整数AA和BB表示询问。

输出格式

对于每个询问按照以下规则分行输出:

1 如果技能AA学完之后才有可能学技能BB;

2 如果技能BB学完之后才有可能学技能AA;

0 除以上两种情况外的其他所有情况。

输入样例

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

输出样例

1
0
0
0
2

数据规模与约定

对于30%30%的数据,有1≤N,Q≤10001≤N,Q≤1000;

对于40%40%的数据,有1≤N≤10001≤N≤1000;

对于60%60%的数据,有1≤Q≤20001≤Q≤2000;

对于100%100%的数据,有1≤N,Q≤400001≤N,Q≤40000,所有技能编号为11至4000040000,有且仅有一个基础技能;

------ 本文结束 ------