倍增模板,在一个严格小根堆中,给定$x,y$,求$x$的祖先中$≥y$的最高点。
注意清零
#include<cstdio>
#include<iostream>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int maxn = 1e5+;
int t,n,q,val[maxn],cnt;
int dpth[maxn],p[maxn][];
int to[maxn],head[maxn],nxt[maxn]; void add(int x,int y) {
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
} void dfs(int x,int fa) {
dpth[x] = dpth[fa]+;
p[x][] = fa;
for(int i = ; (<<i)<=dpth[x]; i++)
p[x][i] = p[p[x][i-]][i-];
for(int i = head[x]; i; i = nxt[i]) {
if(to[i] == fa)continue;
dfs(to[i],x);
}
} int solve(int x,int y) {
for(int i = ; i >= ; i--) {
if(val[p[x][i]] >= y) x = p[x][i];
if(x== || val[x]==y)break;
}
return x;
} int main() {
scanf("%d",&t);
for(int j = ;j <= t;j++) {
printf("Case %d:\n",j);
memset(to,,sizeof(to));
memset(head,,sizeof(head));
memset(nxt,,sizeof(nxt));
memset(p,,sizeof(p));
cnt = ;
val[] = ;
dpth[] = ;
scanf("%d%d",&n,&q);
int x,y;
for(int i = ; i <= n-; i++) {
scanf("%d%d",&x,&y);
add(x,i);
val[i] = y;
}
dfs(,);
for(int i = ; i <= q; i++) {
scanf("%d%d",&x,&y);
printf("%d\n",solve(x,y));
}
}
return ;
}