一道裸的LCA板子题，就是卡常有点难受,注释在代码里
代码 #include<bits/stdc++.h> using namespace std; const int maxn=22,maxk=1000005; int f[maxk][maxn]; int head[maxk],tot=1; struct asd{ int to,next,val; }b[maxk>>1]; inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; } inline void write(int x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); } void ad(int aa,int bb,int cc){ b[tot].to=bb; b[tot].next=head[aa]; b[tot].val=cc; head[aa]=tot++; } int dep[maxk]; void dfs(int now,int fa,int da){ f[now][0]=fa; dep[now]=dep[fa]+1; for(int i=1;(1<<i)<=dep[now];i++){ f[now][i]=f[f[now][i-1]][i-1]; } for(int i=head[now];i!=-1;i=b[i].next){ int u=b[i].to; if(u==fa) continue; dfs(u,now,b[i].val); } } int get_LCA(int xx,int yy){ if(dep[xx]<dep[yy]) swap(xx,yy); int len=dep[xx]-dep[yy],k=0; while(len){ if(len&1){ xx=f[xx][k]; } len>>=1; k++; } if(xx==yy) return xx; for(int i=20;i>=0;i--){ if(f[xx][i]==f[yy][i]) continue; xx=f[xx][i]; yy=f[yy][i]; } return f[xx][0]; } int main(){ memset(head,-1,sizeof(head)); int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<n;i++){ int aa,bb; aa=read(),bb=read(); ad(aa,bb,1); ad(bb,aa,1); } dfs(m,0,0); int bef=m; for(int i=1;i<=k;i++){ int aa,bb; aa=read(),bb=read(); int gg=get_LCA(bef,aa);//上一次的位置到现在位置的花费 int tot=dep[aa]+dep[bef]-dep[gg]*2; if(tot<=bb){ write(aa);//如果小于步数，可以达到 printf(" "); bef=aa; } else {//否则 //求出要到达的节点与之前节点的最近公共祖先 int now=dep[bef]-dep[gg];//求出之前节点到公共祖先的距离 if(now>=bb){//如果当前节点到公共祖先的距离大于步数 int ans=bb; int k=0; while(ans){ if(ans&1) bef=f[bef][k]; k++; ans>>=1; } write(bef);//将之前的节点想上跳要到达的步数 printf(" "); } else {//如果当前节点到公共祖先的距离小于步数，则在另一分支 int ans=bb-now;//求出在另一分支上的步数 int zjz=dep[aa]-dep[gg];//求出要到达的节点到最近公共祖先的距离 int zjz2=zjz-ans;//距离减去步数 int k=0; while(zjz2){ if(zjz2&1) aa=f[aa][k]; k++; zjz2>>=1; } write(aa); printf(" "); bef=aa; } } } return 0; } B、虫洞 题目描述我们建两层点，其中\([1,n]\)代表白洞，\([n+1,n\times 2]\)代表黑洞
如果我们建边的时候，如果该边上的两个点都是黑洞或者白洞
那么在我们进行跃进的时候，只需要花费原来的价值就可以
所以我们从\(aa\)到\(bb+n\)，从\(aa+n\)到\(bb\)分别建一条边，权值为输入的权值即可
如果两个点一个是黑洞一个是白洞，我们就按照题目中的要求建边
最后我们还要考虑在某个节点停留的情况
我们需要从\(i\)到\(i+n\)建一条权值为\(0\)的边，代表在白洞停留
从\(i+n\)到\(i\)建一条权值为该点燃料消耗的边，代表在黑洞停留