P6072 『MdOI R1』 Path 题解

南阳刘子骥 · 2023-02-05 21:02:52 · 题解

题目要求我们从一棵树中选出两条互不相交的简单路径，使得其边权异或和之和最大。

首先我们可以将不好维护的边权异或和转化为路径两端点到根的这两条路径上的边权异或和。

然后就是考虑如何不重不漏地找到这两条路径。
可以想到边分治，用当前的分治中心来分开两条路径。但是两条路径的其中一条可能会穿过上层的分治中心，导致维护困难，可以pass掉。

可以想到对于每一个点，分别求出子树内的最大路径和子树外的最大路径，发现可行。

维护子树外的最大路径可以参考P8511这道Ynoi，提供了一种 O(n \log v) 的、利用支配性质的做法，其中 v 是值域。

对于子树内的做法，我们也可以利用支配的性质。
我们首先找到异或和最大的两个点 x 和 y，考虑 a_x \oplus a_y 对答案的贡献。

• 对于 x 和 y 都在子树内的，子树内答案就是 a_x \oplus a_y。这一条适用于从 \operatorname{lca}(x,y) 向上到根的这一条路径上的点。
• 对于 x 和 y 都不在子树内的，子树外答案就是 a_x \oplus a_y，子树内答案就需要单独计算并取较大值即可。其中我们可以利用贪心策略，对于一棵子树，我们只需要计算其根的子树内答案即可。这一条适用于所有不在 x 到根或 y 到根路径上的子树。
• 对于 x 和 y 两者中只有一个在子树中的，我们也需要单独计算其子树内答案。这一条适用于 x 到 \operatorname{lca}(x,y) 再到 y 这两条路径上的点。

分析一下时间复杂度：

首先子树外的答案是 O(n \log v) 的。
其次，子树内的答案的三部分我们分别分析：

• 第一部分直接统计 O(n)；
• 第二部分，我们只对于每一棵极大子树的根节点统计答案，那么这棵子树内的每一个节点只会被插入一次，总共就只会插入 O(n) 级别的节点，复杂度 O(n \log v)；
• 第三部分，我们可以对于两条路径分别从下往上统计答案，此时我们只需要插入操作即可统计，总共也只会插入 O(n) 级别的节点，复杂度 O(n \log v)。 所以总复杂度是 O(n \log v)。

代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 30010, M = N << 1;
struct Trie
{
    struct Node
    {
        int s[2];
        int end;
    };
    Node tr[N * 30];
    int idx;
    void clear()
    {
        for(int i = 0; i <= idx; i++)
            tr[i].s[0] = tr[i].s[1] = tr[i].end = 0;
        idx = 0;
    }
    void insert(int x, int id)
    {
        int p = 0;
        for(int i = 29; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(!tr[p].s[c])tr[p].s[c] = ++idx;
            p = tr[p].s[c];
        }
        tr[p].end = id;
    }
    int query(int x)
    {
        int p = 0;
        for(int i = 29; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(tr[p].s[c ^ 1])p = tr[p].s[c ^ 1];
            else if(tr[p].s[c])p = tr[p].s[c];
            else return 0;
        }
        return tr[p].end;
    }
};

int n;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int a[N], ans[N];
Trie tr;
int l1, l2; int maxn;
int dep[N], fa[N], deg[N];
bool tag[N];
void dfs1(int p, int fa, int v)
{
    dep[p] = dep[fa] + 1, ::fa[p] = fa, a[p] = v;
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa)continue;
        dfs1(e[i], p, v ^ w[i]);
    }
}
int lca(int p, int q)
{
    if(dep[p] < dep[q])swap(p, q);
    tag[p] = tag[q] = true;
    while(dep[p] > dep[q])p = fa[p], tag[p] = true;
    if(p == q)return p;
    while(p != q)p = fa[p], q = fa[q], tag[p] = tag[q] = true;
    return p;
}
int sta[N], tt;
bool vis[N];
void dfs2(int p, int fa)
{
    tr.insert(a[p], p);
    int q = tr.query(a[p]);
    if((a[p] ^ a[q]) > maxn)maxn = a[p] ^ a[q];
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa || vis[e[i]])continue;
        dfs2(e[i], p);
    }
}
void solve(int p, int q)
{
    if(p == q)return;
    if(dep[p] < dep[q])swap(p, q);
    tt = 0;
    while(p != q)sta[++tt] = p, vis[p] = true, p = fa[p];
    tr.clear(), maxn = 0;
    dfs2(1, 0);
    for(int i = tt; i; i--)
    {
        ans[sta[i]] = maxn;
        dfs2(sta[i], fa[sta[i]]);
        vis[sta[i]] = false;
    }
}
int res = 0;
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    bool flag = true;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
        deg[u]++, deg[v]++;
        if(deg[u] > 2 || deg[v] > 2)flag = false;
    }
    dfs1(1, 0, 0);
    tr.clear(), maxn = 0;
    for(int i = 1; i <= n; i++)
    {
        tr.insert(a[i], i);
        int j = tr.query(a[i]);
        if((a[i] ^ a[j]) > maxn)l1 = j, l2 = i, maxn = a[i] ^ a[j];
    }
    //求子树外的答案
    int g = lca(l1, l2);
    for(int i = g; i >= 1; i = fa[i])tag[i] = true;
    for(int i = 2; i <= n; i++)
        if(!tag[i])ans[i] = maxn;
    solve(1, l1), solve(g, l2);
    //一条链且x到y是整条链的特殊情况
    if(flag && deg[l1] == 1 && deg[l2] == 1)
    {
        tr.clear(), maxn = 0;
        if(deg[l2] < deg[l1])swap(l1, l2);
        for(int i = l2; i != l1; i = fa[i])
        {
            tr.insert(a[i], i);
            int j = tr.query(a[i]);
            if((a[i] ^ a[j]) > maxn)maxn = a[i] ^ a[j];
            res = max(res, ans[i] + maxn);
        }
        printf("%d\n", res);
        return 0;
    }
    //x与y均在子树内的点
    for(int i = g; i >= 1; i = fa[i])
        res = max(res, ans[i] + (a[l1] ^ a[l2]));
    //x与y均在子树外的点
    queue<int>q;
    for(int i = l1; i != g; i = fa[i])
    {
        for(int j = h[i]; ~j; j = ne[j])
            if(!tag[e[j]])q.push(e[j]);
    }
    for(int i = l2; i != g; i = fa[i])
    {
        for(int j = h[i]; ~j; j = ne[j])
            if(!tag[e[j]])q.push(e[j]);
    }
    for(int i = h[g]; ~i; i = ne[i])
        if(!tag[e[i]])q.push(e[i]);
    for(int i = 1; i <= n; i++)vis[i] = false;
    while(!q.empty())
    {
        tr.clear(), maxn = 0;
        dfs2(q.front(), fa[q.front()]);
        res = max(res, maxn + (a[l1] ^ a[l2]));
        q.pop();
    }
    res = max(res, maxn + (a[l1] ^ a[l2]));
    //x到y路径上的点
    tr.clear(), maxn = 0;
    for(int i = 1; i <= n; i++)vis[i] = false;
    for(int i = l1; i != fa[g]; i = fa[i])
    {
        dfs2(i, fa[i]);
        vis[i] = true;
        res = max(res, maxn + ans[i]);
    }
    tr.clear(), maxn = 0;
    for(int i = 1; i <= n; i++)vis[i] = false;
    for(int i = l2; i != fa[g]; i = fa[i])
    {
        dfs2(i, fa[i]);
        vis[i] = true;
        res = max(res, maxn + ans[i]);
    }

    printf("%d\n", res);
    return 0;
}