[ONTAK2015]Związek Harcerstwa Bajtockiego

题目大意：

一棵\(n(n\le10^6)\)个点的树，从\(m\)出发，依次执行\(k(k\le10^6)\)条操作，每次操作从当前点出发，向着点\(d\)前进\(t\)步，求每次操作完成后所在的位置。

思路：

使用树剖/倍增等LCA算法依题意模拟即可。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e6+1;

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

	e[v].push_back(u);

}

int dep[N],par[N],top[N],size[N],son[N],dfn[N],id[N];

void dfs(const int &x,const int &par) {

	size[x]=1;

	::par[x]=par;

	dep[x]=dep[par]+1;

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par) continue;

		dfs(y,x);

		size[x]+=size[y];

		if(size[y]>size[son[x]]) {

			son[x]=y;

		}

	}

}

void dfs(const int &x) {

	dfn[x]=++dfn[0];

	id[dfn[x]]=x;

	top[x]=x==son[par[x]]?top[par[x]]:x;

	if(son[x]) dfs(son[x]);

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par[x]||y==son[x]) continue;

		dfs(y);

	}

}

inline int lca(int x,int y) {

	while(top[x]!=top[y]) {

		if(dep[top[x]]<dep[top[y]]) {

			std::swap(x,y);

		}

		x=par[top[x]];

	}

	return dep[x]<dep[y]?x:y;

}

inline int jump(int x,int t) {

	while(dep[x]-dep[top[x]]+1<=t) {

		t-=dep[x]-dep[top[x]]+1;

		x=par[top[x]];

	}

	return id[dfn[x]-t];

}

inline int walk(int x,int y,int t) {

	const int z=lca(x,y),d=dep[x]+dep[y]-dep[z]*2;

	t=std::min(d,t);

	if(t<=dep[x]-dep[z]) {

		return jump(x,t);

	} else {

		return jump(y,d-t);

	}

}

int main() {

	const int n=getint();

	int x=getint();

	const int k=getint();

	for(register int i=1;i<n;i++) {

		add_edge(getint(),getint());

	}

	dfs(1,0);

	dfs(1);

	for(register int i=1;i<=k;i++) {

		const int y=getint(),t=getint();

		printf("%d%c",x=walk(x,y,t)," \n"[i==k]);

	}

	return 0;

}