Skip to content

11375: 【原1375】祖孙询问

题目

题目描述

author: yuan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1375 

题目描述

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

输入说明

输入第一行包括一个整数n表示节点个数。

接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1,那么a就是树的根。

第n+2行是一个整数m表示询问个数。

接下来m行,每行两个正整数x和y。

输出说明

对于每一个询问,输出1如果x是y的祖先,输出2如果y是x的祖先,否则输出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%的数据,n,m<=1000。

对于100%的数据,n,m<=40000,每个节点的编号都不超过40000。

q4x3's solution

/**
 * 我真的很讨厌二进制相关的东西
 * 所以讨厌倍增法
 * 请允许我
 * 转成rmq之后线段树
 * 谢谢
 * 一开始忘了双向建边要开两倍空间了,憨憨QAQ
 **/
#include <iostream>
#include <cstdio>
const int MAXN = 8e4 + 233;
bool vis[MAXN];
int to[MAXN], next[MAXN], head[MAXN], depth[MAXN], first[MAXN], dfscache[10 * MAXN];
int tree[40 * MAXN], treepos[40 * MAXN];
int n, m, tmp, tmpp, dfscnt, k, mini, maxi, root, cnt;

inline void read(int &x) {
    x = 0;
    char ch;
    bool f = 0; 
    while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
    if (ch == '-') f = 1;
    else x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
    x = f ? -x : x;
}

void link(int u, int v, int num) {
    to[num] = v, next[num] = head[u], head[u] = num;
}

void dfs(int rt) {
    vis[rt] = 1;
    ++ dfscnt;
    dfscache[dfscnt] = rt;
    if(first[rt] == 0) first[rt] = dfscnt;
    for(int i = head[rt];i != 0;i = next[i]) {
        if(vis[to[i]]) continue;
        depth[to[i]] = depth[rt] + 1;
        dfs(to[i]);
        ++ dfscnt;
        dfscache[dfscnt] = rt;
    }
}

void build(int rt, int l, int r) {
    if(l == r) {
        tree[rt] = depth[dfscache[l]];
        treepos[rt] = dfscache[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    int tmp1 = tree[rt << 1], tmp2 = tree[rt << 1 | 1];
    if(tmp1 < tmp2) {
        tree[rt] = tmp1;
        treepos[rt] = treepos[rt << 1];
    } else {
        tree[rt] = tmp2;
        treepos[rt] = treepos[rt << 1 | 1];
    }
}

int query(int rt, int l, int r, int s, int t) {
    if(s <= l && r <= t) {
        return treepos[rt];
    }
    int mid = (l + r) >> 1;
    if(t <= mid) return query(rt << 1, l, mid, s, t);
    else if(s > mid) return query(rt << 1 | 1, mid + 1, r, s, t);
    else {
        int tmp1 = query(rt << 1, l, mid, s, t), tmp2 = query(rt << 1 | 1, mid + 1, r, s, t);
        return (depth[tmp1] < depth[tmp2]) ? tmp1 : tmp2;
    }
}

int main() {
    read(n);
    for(int i = 1;i <= n;++ i) {
        read(tmp); read(tmpp);
        if(tmpp == -1) {
            root = tmp;
            continue;
        }
        link(tmp, tmpp, ++ cnt);
        link(tmpp, tmp, ++ cnt);
    }
    depth[root] = 1;
    dfs(root);
    build(1, 1, dfscnt);
    read(m);
    for(int i = 0;i < m;++ i) {
        read(tmp); read(tmpp);
        mini = first[tmp];
        maxi = first[tmpp];
        if(mini < maxi) {
            int tmp0 = query(1, 1, dfscnt, mini, maxi);
            if(tmp0 == tmp) printf("1\n");
            else if(tmp0 == tmpp) printf("2\n");
            else printf("0\n");
        } else {
            int tmp0 = query(1, 1, dfscnt, maxi, mini);
            if(tmp0 == tmp) printf("1\n");
            else if(tmp0 == tmpp) printf("2\n");
            else printf("0\n");
        }
    }
    return 0;
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
struct node;
struct son {
    son* next;
    node* value;
    son(son* next = nullptr, node* value = nullptr) : next(next), value(value){};
};
struct node {
    int height;
    son* sons;
    node() : height(0),
             sons(nullptr) {}
};
//size!
node tree[50000];
node* oila[100000];
int st[100000][30];
int first[50000] = {0};
inline int lg(int n) { return n ? lg(n / 2) + 1 : -1; }
int dfs(node**& oilaptr, node* root, int height) {
    if (first[root - tree])
        return 0;
    first[root - tree] = oilaptr - oila;
    *oilaptr           = root;
    oilaptr++;
    root->height = height;
    son* sss     = root->sons;
    while (sss != nullptr) {
        if (dfs(oilaptr, sss->value, height + 1)) {
            *oilaptr = root;
            oilaptr++;
        }
        sss = sss->next;
    }
    return 1;
}

int main() {
    int n, m, g, r;
    scanf("%d", &n);
    node* root;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &g, &r);
        if (r == -1 || g == -1) {
            root = r == -1 ? tree + g : tree + r;
            continue;
        }
        tree[g].sons = new son(tree[g].sons, tree + r);
        tree[r].sons = new son(tree[r].sons, tree + g);
    }
    node** oilaptr = oila + 1;
    //obey to 1-base
    dfs(oilaptr, root, 1);
    for (int i = 1; i <= oilaptr - oila - 1; i++) {
        st[i][0] = i;
    }
    for (int j = 1; j <= lg(oilaptr - oila - 1); j++) {
        for (int i = 1; i + (1 << j) <= oilaptr - oila; i++) {
            st[i][j] = oila[st[i][j - 1]]->height < oila[st[i + (1 << (j - 1))][j - 1]]->height ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
        }
    }
    scanf("%d", &m);
    int pos, rr, ll, pent;
    while (m--) {
        scanf("%d%d", &ll, &rr);
        ll         = first[ll];
        rr         = first[rr];
        bool swapf = false;
        if (ll > rr) {
            ll ^= rr;
            rr ^= ll;
            ll ^= rr;
            swapf = true;
        }
        if (oila[st[ll][lg(rr - ll + 1)]]->height < oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]]->height) {
            if (first[oila[st[ll][lg(rr - ll + 1)]] - tree] == ll)
                printf(swapf ? "2\n" : "1\n");
            else if (first[oila[st[ll][lg(rr - ll + 1)]] - tree] == rr)
                printf(swapf ? "1\n" : "2\n");
            else
                printf("0\n");
        } else {
            if (first[oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]] - tree] == ll)
                printf(swapf ? "2\n" : "1\n");
            else if (first[oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]] - tree] == rr)
                printf(swapf ? "1\n" : "2\n");
            else
                printf("0\n");
        }
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 40005
using namespace std;
struct Node {
    int x, y;
    Node(int p = 0, int q = 0): x(p), y(q) {}
} query_seq[MAX_N];
int N, Q, root;
vector<int> link[MAX_N], query[MAX_N];
int ans[MAX_N], father[MAX_N];
bool vis[MAX_N], par[MAX_N];
inline int read() {
    char ch = getchar(); int flag = 1, res = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
int Find(int x) {
    if (father[x] != x)
        father[x] = Find(father[x]);
    return father[x];
}
void Union(int x, int y) {
    int p = Find(x), q = Find(y);
    father[p] = q;
}
void tarjan(int x) {
    par[x] = true;
    for (register int i = 0; i < link[x].size(); ++i) {
        int next = link[x][i];
        // not the parent node
        if (!par[next]) {
            tarjan(next);
            Union(next, x);
        }
    }
    vis[x] = true;
    // solve the queries
    for (register int i = 0; i < query[x].size(); ++i) {
        int query_id = query[x][i], node_1 = query_seq[query_id].x, node_2 = query_seq[query_id].y;
        if (vis[node_1] && vis[node_2]) {
            int LCA = Find(x == node_1 ? node_2 : node_1);
            if (LCA == node_1) ans[query_id] = 1;
            else if (LCA == node_2) ans[query_id] = 2;
        }
    }
}
int main() {
    // init tree
    N = read();
    for (register int i = 1; i <= MAX_N; ++i) father[i] = i;
    for (register int i = 0; i < N; ++i) {
        int x = read(), y = read();
        if (x != -1 && y != -1) {
            link[x].push_back(y);
            link[y].push_back(x);
        }
        else if (x == -1) root = y;
        else root = x;
    }
    // input queries
    Q = read();
    for (register int i = 0; i < Q; ++i) {
        int x = read(), y = read();
        query_seq[i].x = x;
        query_seq[i].y = y;
        // record the query_id related to the two node
        query[x].push_back(i);
        query[y].push_back(i);
    }
    // find LCA of each query
    tarjan(root);
    // output the answers
    for (register int i = 0; i < Q; ++i)
        printf("%d\n", ans[i]);
    return 0;
}