传送门:?id=4281
反正已经没有人来这里了……我想怎么BB就怎么BB……aha
倍增树剖水题一道……拿来敲敲键盘
这么水为什么还没有多少人做……现在的年轻人都不刷bzoj吗？
跪求哪个偶尔光顾这里的年轻人告诉我这个老头你们都在做哪个OJ
Code:
#include<bits/stdc++.h>using namespace std;const int maxn=1e6+1;const int BIT=20;int n,m,k;int fa[maxn][BIT],dep[maxn];vector<int>G[maxn];void dfs(int u){for(int i=1;i<BIT;i++)if(fa[u][i-1])fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=0;i<G[u].size();i++){int v=G[u][i];if(fa[u][0]!=v){fa[v][0]=u;dep[v]=dep[u]+1;dfs(v);}}}int lca(int u,int v){if(dep[u]<dep[v])swap(u,v);int d=dep[u]-dep[v];for(int i=BIT-1;i>=0;i–)if(d>>i&1)u=fa[u][i];if(u==v)return u;for(int i=BIT-1;i>=0;i–)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];}int dis(int u,int v){if(dep[u]<dep[v])swap(u,v);int ans=0;int d=dep[u]-dep[v];for(int i=BIT-1;i>=0;i–)if(d>>i&1)u=fa[u][i],ans+=1<<i;if(u==v)return ans;for(int i=BIT-1;i>=0;i–)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i],ans+=(1<<i)*2;return ans+2;}int up(int x,int d){for(int i=BIT-1;i>=0;i–)if(d>>i&1)x=fa[x][i];return x;}int now;int in(){int r=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))r=r*10+c-'0',c=getchar();return r;}int main(){scanf("%d%d%d",&n,&now,&m);for(int i=1;i<n;i++){int u=in(),v=in();G[u].push_back(v);G[v].push_back(u);}dfs(1);while(m–){int d,t,D;t=in();d=in();d=min(d,n);int LCA=lca(now,t);if(dis(now,t)<=d){printf("%d",now=t);}elseif((D=dis(now,LCA))>d){printf("%d",now=up(now,d));}else{printf("%d",now=up(t,dis(LCA,t)-(d-D)));}if(m==-1)puts("");else putchar(' ');}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
回首往事，日子里竟全是斑澜的光影，
