[ABC267F] Exactly K Steps 题解
思路
首先发现,如果对于查询 \((u, k), k > 0\) 可行,那么对于 \((u, k - 1)\) 也一定可行,因为往回走一步就可以了,所以对于一个点可以找到离它最远的点,根据直径的结论,这个点一定是直径的端点之一。
为了方便做,以直径的端点之一为根,然后写一个 K 级祖先稍微分讨一下就搞好了。
时间复杂度:\(O(n\log n + q\log n)\)。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
//#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, q;
vector<int> g[N];
int dist[2][N], A, B, f[N][20], dep[N];
void dfs(int dist[], int u, int fa) {
f[u][0] = fa;
for(int i = 1; i < 20; i ++)
f[u][i] = f[f[u][i - 1]][i - 1];
for(auto v : g[u]) {
if(v == fa) continue;
dist[v] = dist[u] + 1;
dep[v] = dep[u] + 1;
dfs(dist, v, u);
}
}
int LCA(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
for(int i = 19; i >= 0; i --)
if(dep[f[a][i]] >= dep[b])
a = f[a][i];
if(a == b) return a;
for(int i = 19; i >= 0; i --)
if(f[a][i] != f[b][i])
a = f[a][i],
b = f[b][i];
return f[a][0];
}
int jump(int u, int k) {
for(int i = 20; i >= 0; i --)
if(k >= (1 << i)) u = f[u][i], k -= (1 << i);
return u;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1, a, b; i < n; i ++) {
cin >> a >> b;
g[a].push_back(b), g[b].push_back(a);
} cin >> q;
dfs(dist[0], 1, 1);
for(int i = 1; i <= n; i ++) if(dist[0][i] > dist[0][A]) A = i;
dep[A] = 0, dfs(dist[1], A, A);
for(int i = 1; i <= n; i ++) if(dist[1][i] > dist[1][B]) B = i;
dist[0][B] = 0;
dfs(dist[0], B, 0),
dist[1][A] = 0, dep[A] = 0;
dfs(dist[1], A, 0);
for(int i = 1, x, y; i <= q; i ++) {
cin >> x >> y;
if(max(dist[0][x], dist[1][x]) < y) cout << -1 << '\n';
else {
if(dep[x] >= y) {
cout << jump(x, y) << '\n';
continue;
}
int lca = LCA(B, x);
y -= dep[x] - dep[lca];
cout << jump(B, dep[B] - dep[lca] - y) << '\n';
}
}
return 0;
}
标签:dist,int,题解,Exactly,dfs,dep,Steps,include
From: https://www.cnblogs.com/MoyouSayuki/p/17929408.html