6, 7, 8 三个测试点 RE

求助,怀疑是数据问题。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5, logn = 18;
int n, m, dep[maxn + 3], mx[maxn + 3], ch[maxn + 3], fa[maxn + 3][logn + 3];
int top[maxn + 3], bot[maxn + 3], len[maxn + 3], ans, lg[maxn + 3];
vector<int> G[maxn + 3], S[maxn + 3];

void dfs(int u, int pa = 0) {
    for (int i = 1; (fa[u][i] = fa[fa[u][i - 1]][i - 1]); i++);
    for (int i = 0, v; i < G[u].size(); i++) {
        v = G[u][i];
        if (v == pa) continue;
        fa[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        if (mx[v] + 1 > mx[u]) {
            mx[u] = mx[v] + 1, ch[u] = v;
        }
    }
}

void solve(int u, int pa = 0, int t = 1) {
    top[u] = t;
    for (int i = 0, v; i < G[u].size(); i++) {
        v = G[u][i];
        if (v == pa || v == ch[u]) continue;
        solve(v, u, v);
    }
    if (ch[u]) {
        len[top[u]]++;
        solve(ch[u], u, t);
    } else {
        bot[top[u]] = u;
    }
    S[top[u]].push_back(u);
    if (u == t) {
        for (int i = 1, x = u; i <= len[u]; i++) {
            S[u].push_back(x = fa[x][0]);
        }
    }
}

int query(int x, int k) {
    if (k == 0) {
        return x;
    } else if (k > dep[x]) {
        return 0;
    }
    int t = lg[k];
    x = fa[x][t], k -= 1 << t;
    return S[top[x]][dep[bot[top[x]]] - dep[x] + k];
}

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1);
    solve(1);
    scanf("%d", &m);
    for (int x, k; m --> 0; ) {
        scanf("%d %d", &x, &k);
        x ^= ans, k ^= ans;
        printf("%d\n", ans = query(x, k));
    }
    return 0;
}

0 条评论

目前还没有评论...

信息

难度
8
分类
数据结构 点击显示
标签
递交数
2172
已通过
181
通过率
8%
上传者