Problem
Solution
设 \(s[u]\) 是根到 \(u\) 路径上的异或和,树上任意两点 \(u,v\) 的路径异或和可表示为 \(s[u] \oplus s[v]\)。
考虑查询操作 ? v x
即求 \(\max\{ s[v] \oplus s[u] \oplus x |\ \ 1 \le u \le n, u \not = v\}\) ,若把 \(s[v] \oplus x\) 看作一个整体,这恰好是 01Trie 可以解决的问题。
考虑修改操作 ^ y
对查询的影响:由于是全局 \(\oplus y\),当路径长度为偶数时对结果没有影响,路径长度为奇数时则会有影响。于是我们可以开两个 01Tire,将树黑白染色,同一颜色的 \(s[u]\) 存入相同的 01Trie。同色点间的路径长度一定为偶数,反之不同颜色点间的路径长度一定为奇数。
注意到查询时,01Tire对应的集合里面不应该有自己,所以要涉及到 01Trie的删除操作。
时间复杂度 \(O(n*30)\)
Code
Talk is cheap.Show me the code
#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
typedef pair<int,int> pii;
const int N = 2e5+7;
const int MAXN = 6e6+7;
int n,m;
int val[N];
bool tp[N];
vector<pii> E[N];
struct Trie {
int tot;
int cnt[MAXN];
int ch[MAXN][2];
void Init() {
for(int i=0;i<=tot;++i) {
cnt[i] = ch[i][0] = ch[i][1] = 0;
}
tot = 0;
}
void insert(int x,int k) {
int now = 0;
for(int i=30;i>=0;--i) {
int c = (x>>i)&1;
if(!ch[now][c]) ch[now][c] = ++tot;
now = ch[now][c];
cnt[now] += k;
}
}
int find_max(int x) {
int now = 0, res = 0;
for(int i=30;i>=0;--i) {
int c = (x>>i)&1;
if(ch[now][c^1] && cnt[ch[now][c^1]]) now = ch[now][c^1], res |= (1<<i);
else {
if(!(ch[now][c] && cnt[ch[now][c]])) return -1;
now = ch[now][c];
}
}
return res;
}
}tree[2];
void Dfs(int u,int fa,int s) {
tree[s].insert(val[u], 1);
tp[u] = s;
for(auto now : E[u]) {
int v = now.first, w = now.second;
if(v == fa) continue;
val[v] = val[u] ^ w;
Dfs(v, u, s^1);
}
}
void solve() {
n = read(), m = read();
for(int i=1;i<n;++i) {
int u = read(), v = read(), w = read();
E[u].push_back(mp(v, w));
E[v].push_back(mp(u, w));
}
Dfs(1, 0, 0);
int y = 0;
while(m--) {
char op;
cin >> op;
if(op == '^') {
int x = read(); y ^= x;
} else {
int v = read(), x = read();
tree[tp[v]].insert(val[v], -1);
int mx1 = tree[tp[v]].find_max(val[v]^x);
int mx2 = tree[tp[v]^1].find_max(val[v]^x^y);
printf("%d\n",max(mx1, mx2));
tree[tp[v]].insert(val[v], 1);
}
}
for(int i=1;i<=n;++i) {
E[i].clear();
val[i] = tp[i] = 0;
}
tree[0].Init();
tree[1].Init();
}
int main()
{
int T = read();
while(T--) {
solve();
}
return 0;
}
Summary
01 Trie 可以解决的问题:
- 某一个数与集合中的一个数的异或最大值。