JZOJ3054 祖孙询问 题解
Description
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。
Input
输入第一行包括一个整数n表示节点个数。
接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。
第n+2行是一个整数m表示询问个数。
接下来m行，每行两个正整数x和y。
Output
对于每一个询问，输出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
Hint
对于100%的.n,m≤40000，每个节点的编号都不超过40000。
典型的一眼题。
两个解法：
1.各种LCA算法。如果u是v的祖先那么LCA(u, v) == u，反之LCA(u, v) == v说明v是u的祖先，如果LCA(u, v)既不等于u也不等于v，那么两个点没有关系。
解法1代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int N = 4e4 + 3;
int root, n, m, u, v, tot = 0;
int st[N], to[N << 1], nx[N << 1], f[N][21], dep[N], buc[N];
inline int read()
{
int x = 0, f = 0;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1;
for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0');
return f ? -x : x;
}
inline void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot; }
inline void swap(int &a, int &b) { int t = a; a = b, b = t; }
void dfs(int u)
{
for (int i = st[u]; i; i = nx[i])
{
int v = to[i];
if (v != f[u][0])
f[v][0] = u, dep[v] = dep[u] + 1, dfs(v);
}
}
int LCA(int u, int v)
{
if (dep[v] > dep[u]) swap(u, v);
for (int i = 20; i >= 0; i--)
if (dep[f[u][i]] >= dep[v])
u = f[u][i];
if (u == v) return u;
for (int i = 20; i >= 0; i--)
if (f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
return f[u][0];
}
void init()
{
n = read();
for (int i = 1; i <= n; i++)
{
u = read(), v = read();
if (v == -1) root = u; //记录根节点
else
{
add(u, v), add(v, u);
buc[u] = buc[v] = 1;
}
}
f[root][0] = 0, dep[root] = 1, dfs(root);
//采用倍增LCA
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= 40000; i++)
if (buc[i]) f[i][j] = f[f[i][j - 1]][j - 1];
}
void solve()
{
m = read();
while (m--)
{
u = read(), v = read();
if (u == v || !buc[u] || !buc[v]) printf("0
"); //这个判断貌似是多余的
else
{
int lca = LCA(u, v); //求出LCA
if (lca == u) printf("1
");
else if (lca == v) printf("2
");
else printf("0
");
}
}
}
int main()
{
init();
solve();
return 0;
}
2.dfs序。记录每个节点的dfs序和size，u的子树范围(dfsn[u]表示u的dfs序)是dfsn[u]~dfsn[u] + size[u] - 1，如果dfsn[v]在这个范围内，那么u是v的祖先，反之亦然。
解法2代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int N = 4e4 + 3;
int n, u, v, q, root, tot = 0, cnt = 0;
int st[N], to[N << 1], nx[N << 1], tid[N], siz[N];
inline int read()
{
int x = 0, f = 0;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1;
for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0');
return f ? -x : x;
}
inline void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot; }
void dfs(int u, int from)
{
tid[u] = ++cnt, siz[u] = 1; //记录dfs序和size
for (int i = st[u]; i; i = nx[i])
{
int v = to[i];
if (v != from)
{
dfs(v, u);
siz[u] += siz[v]; 累加子树的size
}
}
}
void init()
{
n = read();
for (int i = 1; i <= n; i++)
{
u = read(), v = read();
if (v == -1) root = u;
else add(u, v), add(v, u);
}
dfs(root, 0);
}
void solve()
{
q = read();
while (q--)
{
u = read(), v = read();
if (tid[u] <= tid[v] && tid[v] <= tid[u] + siz[u] - 1) printf("1
"); //u是v的祖先
else if (tid[v] <= tid[u] && tid[u] <= tid[v] + siz[v] - 1) printf("2
"); //v是u的祖先
else printf("0
"); //都不是
}
}
int main()
{
init();
solve();
return 0;
}
终于有那么一道可以做的题目了。