题解 P2633 【Count on a tree】
Ireliaღ
2019-08-31 15:31:47
**值域主席树能做的事情,可持久化Trie都能做到**
所以,我们可以用可持久化Trie来做这道题
## 解题思路
- 对于每一个树上的点,建一个版本的Trie,来存储从根到该点路径上的所有数。可见,在每一个节点上,我们需要以父节点的Trie作为原版本来添加
- 为了得到$a$、$b$路径上的所有数的信息,我们可以用$a+b-lca-lcafa$来求出。直接在这几个Trie上一起往下走路,对$size$做和差即可,基本框架和Trie求全局第$k$小一样,关于Trie求区间第$k$小可以看[这篇题解](https://www.luogu.org/blog/126376/solution-p3834)
## 程序实现
树剖+Trie
```cpp
// luogu-judger-enable-o2
#include <iostream>
using std :: cin;
using std :: cout;
using std :: swap;
using std :: cerr;
typedef unsigned int U;
const int MAXN = 1e5 + 5;
struct Edge{
int to;
Edge *nxt;
Edge() {}
Edge(int to, Edge *nxt) : to(to), nxt(nxt) {}
}epool[MAXN << 1];
Edge *head[MAXN];
Edge *NewEdge(int to, Edge *nxt) {
static int cnt = 0;
epool[cnt] = Edge(to, nxt);
return &epool[cnt++];
}
void AddEdge(int u, int v) {
head[u] = new Edge(v, head[u]);
}
int n, m;
int a[MAXN];
int fa[MAXN], dep[MAXN], son[MAXN], siz[MAXN], top[MAXN], idx[MAXN];
int idcnt;
void Dfs1(int u, int las, int depth) {
fa[u] = las;
dep[u] = depth;
siz[u] = 1;
for (Edge *e = head[u]; e; e = e->nxt) {
int v = e->to;
if (v == fa[u]) continue;
Dfs1(v, u, depth + 1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void Dfs2(int u, int topf) {
top[u] = topf;
idx[u] = ++idcnt;
if (!son[u]) return;
Dfs2(son[u], topf);
for (Edge *e = head[u]; e; e = e->nxt) {
int v = e->to;
if (v == fa[u] || v == son[u]) continue;
Dfs2(v, v);
}
}
int Lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) swap(x, y);
y = fa[top[y]];
}
if (dep[x] > dep[y]) swap(x, y);
return x;
}
struct Node{
int siz;
Node *ch[2];
}npool[10000000];
void Update(Node *now) {
now->siz = (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0);
}
Node *NewNode() {
static int cnt = 0;
npool[cnt].siz = 0;
npool[cnt].ch[0] = NULL;
npool[cnt].ch[1] = NULL;
return &npool[cnt++];
}
Node *Copy(Node *now) {
Node *ret = NewNode();
*ret = *now;
return ret;
}
Node *rt[MAXN];
void Insert(Node *&now, U num, int base) {
if (!now) now = NewNode();
else now = Copy(now);
if (base == 0) {
now->siz++;
return;
}
int f = (num & (1U << base - 1)) ? 1 : 0;
Insert(now->ch[f], num, base - 1);
Update(now);
}
U QueryKth(Node *now1, Node *now2, Node *now3, Node *now4, int base, int k, U res) {
if (base == 0) return res;
int ls1 = (now1 && now1->ch[0]) ? now1->ch[0]->siz : 0;
int ls2 = (now2 && now2->ch[0]) ? now2->ch[0]->siz : 0;
int ls3 = (now3 && now3->ch[0]) ? now3->ch[0]->siz : 0;
int ls4 = (now4 && now4->ch[0]) ? now4->ch[0]->siz : 0;
int ls = ls1 + ls2 - ls3 - ls4;
if (k <= ls) return QueryKth(now1 ? now1->ch[0] : NULL, now2 ? now2->ch[0] : NULL, now3 ? now3->ch[0] : NULL, now4 ? now4->ch[0] : NULL, base - 1, k, res);
else return QueryKth(now1 ? now1->ch[1] : NULL, now2 ? now2->ch[1] : NULL, now3 ? now3->ch[1] : NULL, now4 ? now4->ch[1] : NULL, base - 1, k - ls, res + (1U << base - 1));
}
void Print(Node *now, int base, U res) {
if (!now) return;
if (base == 0) cerr << res << " ";
Print(now->ch[0], base - 1, res);
Print(now->ch[1], base - 1, res | (1U << base - 1));
}
void Dfs3(int u) {
rt[u] = rt[fa[u]];
Insert(rt[u], a[u], 31);
for (Edge *e = head[u]; e; e = e->nxt) {
int v = e->to;
if (v == fa[u]) continue;
Dfs3(v);
}
}
void Init() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
AddEdge(x, y);
AddEdge(y, x);
}
Dfs1(1, 0, 1);
Dfs2(1, 1);
rt[0] = NewNode();
Dfs3(1);
// for (int i = 0; i <= n; i++) {
// cerr << i << " :\n";
// Print(rt[i], 31, 0);
// cerr << "\n";
// }
// cerr << "*";
}
void Work() {
int ans = 0;
for (int i = 1; i <= m; i++) {
int x, y, k;
cin >> x >> y >> k;
x ^= ans;
int lca = Lca(x, y);
ans = QueryKth(rt[x], rt[y], rt[lca], rt[fa[lca]], 31, k, 0);
cout << ans << "\n";
}
}
int main() {
Init();
Work();
return 0;
}
```