F Exactly K Steps
题目：
给出一棵n个点的树，边权为1，进行2e5次询问，每次输出任意一个离结点(u)距离为(k)的结点。
思路：
对于树上问题，我们的武器不多，而且时间复杂度为O(logn)，可以尝试往里套知识点。对于一棵树来说，易知一个结点距离最远的结点是树的直径的两个端点中的一个。通过反证法可以推出该结论，若一个结点距离最远的节点不是树的直径的端点，那么这个点才应该是树的直径端点。
现在我们求出树的直径的左右端点编号，然后判断k是否大于超过了点(u)到最远点的距离，若超过无解；若不超过，必定有解。那么我们如何得到这个解呢？通过倍增LCA就可以在到达距离(u)距离为k的点，对于这个点的位置进行分类讨论即可。
实现：
值得注意的是，用LCA可以求出直径的两个端点。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> g[N];
int dep[N];
int anc[N][35];
void dfs(int u, int fa)
{
anc[u][0] = fa;
for(int j = 1; j <= 30; j ++)
if((1 << j) <= dep[u])
anc[u][j] = anc[anc[u][j - 1]][j - 1];
for(int v : g[u])
{
if(v == fa) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
int LCA(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int j = 30; j >= 0; j --)
if(dep[x] - (1 << j) >= dep[y])
x = anc[x][j];
if(x == y) return x;
for(int j = 30; j >= 0; j --)
if(anc[x][j] != anc[y][j] && (1 << j) <= dep[x])
x = anc[x][j], y = anc[y][j];
return anc[x][0];
}
int dis(int a, int b)
{
int c = LCA(a, b);
return abs(dep[a] - dep[c]) + abs(dep[b] - dep[c]);
}
int find_(int u, int k) //向上跳k次
{
int depth = dep[u] - k;
for(int i = 30; i >= 0; i --)
if(depth <= dep[u] - (1 << i))
u = anc[u][i];
return u;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i < n; i ++)
{
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v); g[v].push_back(u);
}
dfs(1, -1);
int L = 1, R = 1;
for(int i = 1; i <= n; i ++) if(dis(1, i) > dis(1, L)) L = i;
for(int i = 1; i <= n; i ++) if(dis(L, i) > dis(L, R)) R = i;
int m;
scanf("%d", &m);
while(m --)
{
int u, k;
scanf("%d%d", &u, &k);
if(dis(u, R) < dis(u, L)) swap(L, R);
int dist = dis(u, R);
if(k > dist)
printf("-1n");
else
{
if(k <= dis(u, LCA(u, R))) //查看目标点在LCA的左端还是右端
printf("%dn", find_(u, k));
else
printf("%dn", find_(R, dist - k));
}
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
