自动搬运

查看原文

来自洛谷，原作者为

	CTime_Pup_314 **

搬运于2025-08-24 22:17:08，当前版本为作者最后更新于2020-08-05 16:03:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

补充一下这道题的 $O(n\log n\log\max w)$ 的做法，我们以 $1$ 为根，定义 $a_x$ 为从 $x$ 到 $1$ 边权的异或值，$in_x$ 和 $out_x$ 为 $x$ 子树内部和外部选择 $u$ 和 $v$ 中 $a_u\oplus a_v$ 的最大值，那么最后答案显然为 $\max_{x\ne1}\{in_x+out_x\}$。

对于求 $in_x$ 我们有很多做法，例如启发式合并，dsu on tree，或者可持久化 trie，需要 $O(n\log n\log\max w)$ 的时间。

对于求 $out_x$，我们不妨先找到任意两个点 $p$ 和 $q$，使得 $a_p\oplus a_q$ 最大，这时不以这个点对为最大值的只有 $p$ 到根上的所有点，和 $q$ 到根上的所有点。考虑我们只求树上一条链 $out_x$，加入我们按照顺序遍历 到 $x$，只需要将 $x$ 父亲的子树内除去 $x$ 子树部分加入 trie 即可。这一部分复杂度 $O(n\log \max w)$。

通过代码

const int N = 3e4+5, L = 128, S = 1<<7; int SZ;
int n, maxl, p, q, ch[N*L][2], t[N*L], fa[N], tot, tg[N], bel[N], out[N], in[N], a[N], A, B, o[N], rk[N], ans; vector<int> v[N]; vector<pii> e[N]; 
int l2(int x) { return x == 0?-1:l2(x>>1)+1; }
void ins(int &o, int v)
{
    if(!o) o = ++tot; ++t[o];
	for(int i = maxl, x = o; ~i; --i)
	{
		bool d = v>>i&1; if(!ch[x][d]) ch[x][d] = ++tot;
		x = ch[x][d], ++t[x];
	}
}
void cls() { memset(t+1, 0, sizeof(int)*tot); }
int ask(int o, int v)
{
	int ret = 0; 
	for(int i = maxl, x = o; ~i; --i)
	{
		bool d = ~v>>i&1;
		if(t[ch[x][d]]) x = ch[x][d], ret |= 1ll<<i;
		else x = ch[x][d^1];
	}	
	return ret;
}
void mg(int x, int p, int z, int i, int &v)
{
    if(!x) return; if(!~i) return v = max(v, ask(o[p], z)), ins(o[p], z);
    mg(ch[x][0], p, z, i-1, v), mg(ch[x][1], p, z|1<<i, i-1, v);
}
void dfs(int x)
{
    static int _t; rk[++_t] = x, in[x] = 0; ins(o[x], a[x]);
    for(pii u:e[x]) 
    {
        int y = u.fi; if(y == fa[x]) continue;
        fa[y] = x, a[y] = a[x]^u.se, dfs(y); if(t[o[x]] < t[o[y]]) swap(o[x], o[y]);;
        mg(o[y], x, 0, maxl, in[x]), in[x] = max(in[x], in[y]);
    }
}
void sol(int p)
{
	cls(); for(int x = p; x; x = fa[x]) tg[x] = 1; int now = 0;
	for(int k = 1, i; k <= n; v[i].clear(), v[bel[i]].pb(a[i]), ++k) 
		if(tg[i = rk[k]]) bel[i] = i; else bel[i] = bel[fa[i]];
	for(int k = 1, i; k <= n; ++k) if(tg[i = rk[k]])
	{
		for(int w:v[fa[i]]) now = max(now, ask(o[0], w)), ins(o[0], w);
		out[i] = max(out[i], now), tg[i] = 0;
	}
}
int main()
{
	rd(n); for(int i = 1, x, y, z; i < n; ++i) 
        rd(x), rd(y), rd(z), maxl = max(maxl, l2(z)), e[x].pb(pii(y, z)), e[y].pb(pii(x, z));
    dfs(1), cls();
	for(int i = 1; i <= n; ++i) 
	{
		int v = ask(o[0], a[i]); ins(o[0], a[i]), out[i] = -1;
		if((A^B) < v) A = a[i], B = v^A, p = i;
	}
	for(int i = 1; i <= n; ++i) if(a[i] == B) q = i;
	sol(p), sol(q); for(int i = 1; i <= n; ++i) if(!~out[i]) out[i] = A^B;
    for(int i = 2; i <= n; ++i) ans = max(ans, in[i]+out[i]);
    print(ans);
	return 0;
}