题解 P6072 【『MdOI R1』Path】

· · 题解

补充一下这道题的 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;
}