自动搬运

查看原文

来自洛谷，原作者为

	硫酸 这个家伙很懒

搬运于2025-08-24 22:28:00，当前版本为作者最后更新于2023-11-04 17:52:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update on 11.6

添加了解法二，并修改了解法一的小部分内容。

解法一

算是对

先是一个比较套路的转化：记点 $u$ 到根的异或路径为 $dis_u$，则 $a,b$ 间的异或路径就是 $dis_a \oplus dis_b$，那么 Query u v 的答案就是 $\max\limits_{x \in subtree_v } \{ dis_u \oplus dis_x\}$。

如果对于一个点 $v$，将它子树内所有点的 $dis$ 放到一棵 01-trie 上。询问时在 01-trie 从根向叶子走，对于每一位尽可能往 $dis_u$ 相反的方向上走就行了。这一部分也可以参考 P4551 最长异或路径。

问题在于怎么求出每个点的 01-trie 。

考虑树上启发式合并。对于点 $u$，先处理掉所有儿子的 01-trie ，再将重儿子的 01-trie 直接转移到点 $u$ 上，然后把所有轻儿子的 01-trie 合并到 $u$ 上面。

关于复杂度，只有当一个点是轻儿子才会合并。而一条链最多包含 $\log n$ 条重链，于是每个数最多只会添加（包括合并次数）到 01-trie 里 $\log n$ 次，$n$ 个点就是 $n\log n$ 次。每次查询只要在 01-trie 里从根到叶子走一次，也是 $\log n$。

总复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
	template<typename T>inline void read(T &x)
	{
		x=0;int y=1;
		char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
		while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
		x*=y;
		return;
	}
	template<typename T>inline void write(T x)
	{
		if(x<0){putchar('-');x=-x;}
		if(x>9) write(x/10);
		putchar(x%10 + '0');
		return;
	}
}
using namespace IO;
#define writeln(x) write(x),putchar('\n')
#define writesp(x) write(x),putchar(' ')
#define debug printf("Now is on line %d\n",__LINE__)
const int N=2e5+5;
int n=1,Q,tot=0,ans,fa[N],a[N],rt[N],siz[N],hson[N];//rt为每个点上01-trie的根，hson为重儿子
struct Que{int u,v,tim,ans;}inp[N];//离线操作
struct dot{int tim,son[2];}f[N*30];//01-trie
vector<int> w[N],que[N];//w存图，que存每个节点上的询问
int New(int tim)
{
	++tot;f[tot].tim=tim;f[tot].son[0]=0;f[tot].son[1]=0;
	return tot;
}
void add(int id,int x,int dep,int tim)//向01-trie里加入一个数
{
	f[id].tim=min(f[id].tim,tim);
	if(dep<0) return;
	int op=((x>>dep)&1);
	if(!f[id].son[op]) f[id].son[op]=New(tim);
	add(f[id].son[op],x,dep-1,tim);
	return;
}
void merge(int id,int id2,int dep)//合并两个01-trie
{
	if(!id2) return;
	f[id].tim=min(f[id].tim,f[id2].tim);
	if(dep<0) return;
	if(!f[id].son[0]) f[id].son[0]=f[id2].son[0];
	else merge(f[id].son[0],f[id2].son[0],dep-1);
	if(!f[id].son[1]) f[id].son[1]=f[id2].son[1];
	else merge(f[id].son[1],f[id2].son[1],dep-1);
	return;
}
void query(int id,int x,int dep,int tim)//在01-trie里查询
{
	int op=(((x>>dep)&1)^1);//找到数字x第dep位，取反（尽可能往相反方向走）
	if(!f[id].son[op] || f[f[id].son[op]].tim>tim) op^=1;
	ans|=(op<<dep);
	if(dep) query(f[id].son[op],x,dep-1,tim);
	return;
}
void dfs(int id)
{
	siz[id]=1;hson[id]=0;
	for(int to : w[id])
	{
		dfs(to);
		siz[id]+=siz[to];
		if(siz[hson[id]]<siz[to]) hson[id]=to;
	}
	if(hson[id]) swap(rt[id],rt[hson[id]]);//将重儿子（如果有）的01-trie直接转移到当前点
	for(int to : w[id]) merge(rt[id],rt[to],30);//合并其他轻儿子
	for(int i : que[id])
	{
		ans=0;query(rt[id],a[inp[i].u],30,i);
		inp[i].ans=(ans^a[inp[i].u]);
	}
	return;
}
signed main()
{
	int u,v;
	char cc[10];
	rt[1]=New(0);add(rt[1],0,30,0);//细节：初始要在1节点插入一个0，实际意义为走到1节点
	read(Q);
	for(int i=1;i<=Q;++i)
	{
		scanf("%s",cc);read(u);read(v);
		if(cc[0]=='A')
		{
			++n;
			a[n]=(a[u]^v);
			fa[n]=u;
			w[u].emplace_back(n);
			rt[n]=New(i);
			add(rt[n],a[n],30,i);
		}
		else
		{
			inp[i]=Que{u,v,i,0};
			que[v].emplace_back(i);
		}
	}
	dfs(1);
	for(int i=1;i<=Q;++i) if(inp[i].tim) writeln(inp[i].ans);
	return 0;
}

解法二

来自

依然离线，求出 dfs 序，将子树上的查询转化为区间查询。

先开一个数组 $d$，$d_i$ 表示 $dfn_u=i$ 的节点 $u$ 的 $dis_u$。（$dis$ 定义同上）。初始 $d_i=0$，按照操作顺序加入、查询。这样当一个点未加入时，查询到它等价于查询到子树的根，不影响。

然后用树套树维护这个数组 $d$。树状数组套 01-trie，树状数组上第 $i$ 个 01-tire 上存储 $d_1\thicksim d_i$。其中 01-trie 每个节点还要记录这一位出现的次数 $siz$。

查询时，对于 $d_l\thicksim d_r$ ，记第 $r$ 棵 01-tire 和第 $l-1$ 棵“作差”。由于第 $r$ 棵一定是包含第 $l-1$ 棵的，于是将第 $r$ 棵每个节点的 $siz$ 与第 $l-1$ 棵作差，如果为零就是这个点在 $d_l\thicksim d_r$ 中不存在。

作差后得到 $d_l\thicksim d_r$ 的 01-trie ，按解法一中的查询，从根节点走一次就行了。

但是空间很紧，树状数组勉强能在 400MB 混过去，线段树会炸。

代码不是一个人写的，码风不同。

#include <bits/stdc++.h>

#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int N = 2e5 + 5;
const int K = 30;

int n = 1, m, dis[N];
vector<int> e[N];
void Addedge(int u, int v) {
    e[u].push_back(v);
    return ;
}

int cnt, dfn[N], siz[N];
void Dfs(int u) {
    dfn[u] = ++cnt;
    siz[u] = 1;
    for (auto v : e[u])
        Dfs(v), siz[u] += siz[v];
    return ;
}

int tot, rt[N], s[K + 5];
struct Trie { int s[2], siz; } t[N * 200];
void Init(int k) {
    dF(i, K, 1) s[i] = k & 1, k >>= 1;
    return ;
}
void Update(int x, int &rt) {
    Init(x);
    if (!rt) rt = ++tot;
    int u = rt;
    F(i, 1, K) {
        ++t[u].siz;
        if (!t[u].s[s[i]])
            t[u].s[s[i]] = ++tot;
        u = t[u].s[s[i]];
    }
    ++t[u].siz;
    return ;
}

int lowbit(int x) { return x & -x; }
void Update(int x) {
    for (int i = dfn[x]; i <= n; i += lowbit(i))
        Update(dis[x], rt[i]);
    return ;
}
int numl, invl[K], numr, invr[K];
void Init(int l, int r) {
    numl = numr = 0;
    for (int i = r; i; i -= lowbit(i))
        invr[++numr] = rt[i];
    for (int i = l - 1; i; i -= lowbit(i))
        invl[++numl] = rt[i];
    return ;
}
int Query(int l, int r, int x) {
    Init(l, r);
    Init(x);
    int res = 0;
    F(i, 1, K) {
        res <<= 1;
        int sum = 0;//这里把01-trie作差与查询放在一个函数里了
        F(j, 1, numr) sum += t[t[invr[j]].s[s[i] ^ 1]].siz;
        F(j, 1, numl) sum -= t[t[invl[j]].s[s[i] ^ 1]].siz;
        if (sum) {
            res ^= 1;
            F(j, 1, numr) invr[j] = t[invr[j]].s[s[i] ^ 1];
            F(j, 1, numl) invl[j] = t[invl[j]].s[s[i] ^ 1];
        } else {
            F(j, 1, numr) invr[j] = t[invr[j]].s[s[i]];
            F(j, 1, numl) invl[j] = t[invl[j]].s[s[i]];
        }
    }
    return res;
}

string op[N];
int x[N], y[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> m;
    F(i, 1, m) {
        cin >> op[i] >> x[i] >> y[i];
        if (op[i] == "Add")
            Addedge(x[i], ++n),
            dis[n] = dis[x[i]] ^ y[i];
    }
    Dfs(1);
    Update(1);
    int now = 1;
    F(i, 1, m)
        if (op[i] == "Add") Update(++now);
        else cout << Query(dfn[y[i]], dfn[y[i]] + siz[y[i]] - 1, dis[x[i]]) << "\n";
    return 0;
}