洛谷P2633 Count on a tree

\(\large{题目链接}\)
\(\\\)
\(\Large\textbf{Solution: } \large{考虑主席树。回忆主席树板子是在区间上做的，而这里是一颗树。\\那么沿着之前的思想，每一个节点新建一颗树，那么根据差分的思想，路径上的点即为t_u + t_v - t_lca - t_{father[lca]}。\\之后继续沿用区间操作即可。}\)
\(\\\)
\(\Large\textbf{Code: }\)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, m, p, q, sz, a[N], b[N];
int fa[N][20], lg[N], dep[N];
int ls[N << 5], rs[N << 5], sum[N << 5], rt[N << 5];
vector <int> v[N];

int read() {
	char ch = getchar();
	int x = 0, flg = 1;
	while (!isdigit(ch)) { if (ch == ‘-‘) flg = -1; ch = getchar(); }
	while (isdigit(ch)) x = x * 10 + ch - ‘0‘, ch = getchar();
	return x * flg;
}

void dfs1(int x, int f) {
	dep[x] = dep[f] + 1;
	fa[x][0] = f;
	for (int i = 1; (1 << i) <= dep[x]; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for (int i = 0; i < v[x].size(); ++i) if (v[x][i] != f) dfs1(v[x][i], x);
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]]];
	if (x == y) return x;
	for (int i = lg[dep[x]]; i >= 0; --i) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
} 

void build(int &x, int l, int r) {
	int mid = (l + r) / 2; x = ++sz;
	if (l == r) return;
	build(ls[x], l, mid); build(rs[x], mid + 1, r);
}

int update(int x, int l, int r) {
	int cur = ++sz;
	ls[cur] = ls[x], rs[cur] = rs[x], sum[cur] = sum[x] + 1;
	if (l == r) return cur;
	int mid = (l + r) / 2;
	if (mid >= p) ls[cur] = update(ls[cur], l, mid); else rs[cur] = update(rs[cur], mid + 1, r);
	return cur; 
}

void dfs2(int x) {
	p = lower_bound(b + 1, b + 1 + q, a[x]) - b;
	rt[x] = update(rt[fa[x][0]], 1, q);
	for (int i = 0; i < v[x].size(); ++i) {
		int u = v[x][i];
		if (u == fa[x][0]) continue;
		dfs2(u);
	}
}

int query(int x, int y, int ll, int fll, int l, int r, int k) {
	int mid = (l + r) / 2, cur = sum[ls[x]] + sum[ls[y]] - sum[ls[ll]] - sum[ls[fll]];
	if (l == r) return l;
	if (cur >= k) return query(ls[x], ls[y], ls[ll], ls[fll], l, mid, k); else return query(rs[x], rs[y], rs[ll], rs[fll], mid + 1, r, k - cur);
} 

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) a[i] = b[i] = read();
	sort(b + 1, b + 1 + n);
	int x, y;
	for (int i = 2; i <= n; ++i) x = read(), y = read(), v[x].push_back(y), v[y].push_back(x), lg[i] = lg[i >> 1] + 1;
	dfs1(1, 0);
	q = unique(b + 1, b + 1 + n) - b - 1;
	build(rt[0], 1, q);
	dfs2(1);
	int last = 0, k;
	while (m--) {
		x = read(), y = read(), k = read(); x ^= last;
		int lca = LCA(x, y);
		printf("%d\n", last = b[query(rt[x], rt[y], rt[lca], rt[fa[lca][0]], 1, q, k)]);
	}
	return 0;
}

洛谷P2633 Count on a tree

原文：https://www.cnblogs.com/Miraclys/p/12659568.html