abc267 F – Exactly K Steps

题意：

给定一棵树，每次询问 \(u\ k\)，回答任意一个到 \(u\) 的距离距离为 \(k\) 的点

\(n\le 2e5, p\le 2e5\)

思路：

想了很久换根dp+倍增没想出来，对树的直径太不熟悉了

性质：离任一点最远的点必是直径的一个端点

先找直径的两端点 \(L,R\)（我用的 bfs），然后乱搞搞就好啦

法一（不推荐）：\(O(qlogn)\) 倍增

一开始看到这题整个猪脑里就是倍增，写到这里还是想倍增，太sb了

const signed N = 2e5 + 5;
int n, q; vector<int> G[N];

int bfs(int u) { //返回最深的点
    vector<int> q, vis(n + 1);
    int h; q.push_back(u), vis[u] = 1;
    for(h = 0; h < (int)q.size(); h++)
        for(int v : G[q[h]]) if(!vis[v])
            vis[v] = 1, q.push_back(v);
    return q[h - 1];
}

int f[2][N][19];
void dfs(int u, int fa, int f[N][19]) {
    f[u][0] = fa;
    for(int i = 0; f[u][i]; i++)
        f[u][i + 1] = f[f[u][i]][i];
    for(int v : G[u]) if(v != fa)
        dfs(v, u, f);
}
int get(int u, int k, int f[N][19]) {
    for(int i = 0; k; i++, k >>= 1)
        if(k & 1) {
            if(!f[u][i]) return -1;
            else u = f[u][i];
        }
    return u;
}

void sol() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y), G[y].push_back(x);
    }
    
    int l = bfs(1), r = bfs(l);
    dfs(l, 0, f[0]), dfs(r, 0, f[1]);
    
    cin >> q; while(q--) {
        int u, k; cin >> u >> k;
        cout << max(get(u, k, f[0]), get(u, k, f[1])) << '\n';
    }
}

法二：离线询问，dfs找答案，\(O(n)\)

把询问离线下来。考虑dfs栈，dfs到点 \(u\) 时栈中保存着从根到 \(u\) 的树链，在这个链上能找到关于 \(u\) 的所有询问的答案

vector<pair<int, int> > Q[N];
int ans[N];
vector<int> stk;
void dfs(int u, int fa) {
    stk.push_back(u);
    for(auto [k, i] : Q[u])
        if((int)stk.size() - k >= 1)
            ans[i] = stk[(int)stk.size() - 1 - k];
    for(int v : G[u]) if(v != fa)
        dfs(v, u);
    stk.pop_back();
}

void sol() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y), G[y].push_back(x);
    }
    cin >> q;
    for(int i = 1; i <= q; i++) {
        int u, k; cin >> u >> k;
        Q[u].push_back({k, i});
    }
    
    int l = bfs(1), r = bfs(l);
    memset(ans, -1, sizeof ans);
    dfs(l, 0), dfs(r, 0);
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}