「vijos-bashu」lxhgww的奇思妙想(长链剖分)

倍增离线，预处理出爹和孙子们。查询\(O(1)\)
#include <cstdio>

#include <cstring>

#include <numeric>

#include <cmath>

#include <algorithm>

#include <iostream>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define MP make_pair

#ifdef QWQ

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define D_e_Line cerr << "\n--------\n"

#define D_e(x) cerr << (#x) << " : " << x << endl

#define C_e(x) cout << (#x) << " : " << x << endl

#define Pause() system("pause")

#define TIME() fprint(stderr, "TIME : %.3lfms\n", (double)clock() / (double)CLOCKS_PER_SEC)

#include <cassert>

#else

#define FileOpen()

#define FileSave()

#define D_e_Line

#define D_e(x)

#define C_e(x)

#define Pause()

#define TIME()

#endif

struct FastIO {

	template<typename ATP> inline FastIO & operator >> (ATP & x)  {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

		if(f == -1) x = -x;

		return *this;

	}

} io;

using namespace std;

template<typename ATP> inline ATP Max(ATP x, ATP y) {

	return x > y ? x : y;

}

template<typename ATP> inline ATP Min(ATP x, ATP y) {

	return x < y ? x : y;

}

template<typename ATP> inline ATP Abs(ATP x) {

	return x > 0 ? x : -x;

}

#include <vector>

const int N = 3e5 + 7;

vector<int> D[N], U[N];

struct Edge {

	int nxt, pre;

} e[N << 1];

int head[N], cntEdge;

inline void add(int u, int v) {

	e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;

}

int n;

int f[N][21], dep[N], md[N], len[N], son[N], top[N];

inline void DFS_First(int u, int father) {

	f[u][0] = father, md[u] = dep[u] = dep[father] + 1;

	R(i,1,19){

		if(f[u][i - 1]) f[u][i] = f[f[u][i - 1]][i - 1];

		else break;

	}

	for(register int i = head[u]; i; i = e[i].nxt){

		int v = e[i].pre;

		if(v == father) continue;

		DFS_First(v, u);

		if(md[v] > md[son[u]]) son[u] = v, md[u] = md[v];

	}

}

void DFS_Second(int u, int Tp) {

	top[u] = Tp, len[u] = md[u] - dep[Tp] + 1;

	if(!son[u]) return;

	DFS_Second(son[u], Tp);

	for(register int i = head[u]; i; i = e[i].nxt){

		int v = e[i].pre;

		if(v != f[u][0] && v != son[u])

			DFS_Second(v, v);

	}

}

int H[N];

inline void Init() {

	int now = 0;

	R(i,1,n){

		if(!(i & (1 << now))) ++now;

		H[i] = now;

	}

	R(i,1,n){

		if(i == top[i]){

			for(register int j = 1, u = i; j <= len[i] && u; ++j) u = f[u][0], U[i].push_back(u);

			for(register int j = 1, u = i; j <= len[i] && u; ++j) u = son[u], D[i].push_back(u);

		}

	}

}

inline int Query(int u, int K) {

	if(K > dep[u]) return 0;

	if(!K) return u;

	u = f[u][H[K]], K ^= (1 << H[K]);

	if(!K) return u;

	if(dep[u] - dep[top[u]] == K) return top[u];

	if(dep[u] - dep[top[u]] < K) return U[top[u]][K - dep[u] + dep[top[u]] - 1];

	return D[top[u]][dep[u] - dep[top[u]] - K - 1];

}

int main() {

	io >> n;

	R(i,2,n){

		int u, v;

		io >> u >> v;

		add(u, v);

		add(v, u);

	}

	DFS_First(1, 0);

	DFS_Second(1, 1);

	Init();

	int lst = 0, Q;

	io >> Q;

	while(Q--){

		int u, K;

		io >> u >> K;

		u ^= lst, K ^= lst;

		printf("%d\n", lst = Query(u, K));

	}

	return 0;

}
巴特西

「vijos-bashu」lxhgww的奇思妙想(长链剖分)

最新文章

热门文章
