2020-09-17 17:33 已编辑牛客运营

关注

【每日一题】9月17日题目精讲

题号 NC50349
名称 The XOR-longest Path
来源信息学奥赛一本通
 戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

关于trie树的简单介绍：
trie树又叫前缀树，字典树，他用一个树型结构来表示一个字符串集合。树中的每一条边上都有一个字符，从根节点到某一个位置经过的边就是一个字符串，注意因为有的串是另外的串的子串，所以我们可以用一个字符集里没有的字母（比如$)作为字符串结束的标志。这样拥有同样前缀的字符串在树上就会走相同的路径，在储存上节约了空间，在查找目标串时也提高了效率（只需要顺着trie树走下来就好）。
例子：
aab aaaa cba abc caab aa
六个字符串在trie树上表示，如图：
图片说明

特别的，当我们的字符集只有01两种元素的时候，我们可以构造一棵二叉树，0的分支在左边，1的分支在右边，这就是01trie树。它常被用来处理这样一个经典问题：给你若干个数，选出其中两个数使得他们异或之后最小/最大。（这里以最小为例）
我们遍历数组中的元素，对于每个元素在他前面找和他异或起来最小的值，显然，要最小肯定是这两个数要从最高位开始尽量一致，我们把它之前的数都按照二进制串的样子加入到01trie里面（所有数的位数统一成一致，不够的补零）。然后根据当前这个数对应的01串在trie上从根向下走，如果当前数这一位是0，在trie树上我们更希望走0的那一边，有0就往0那边走，没有0就只能走1了。
如图：
图片说明
————————————我是基本知识介绍完毕的分割线—————————————
本题题解
作者：。。。201910131627798
原博客链接：https://blog.nowcoder.net/n/e09c16c6b0a14c2ba959aa740b98bbf0

分析

在一颗树上寻找一条异或值最大的简单路径。先考虑到异或有如下性质 $a \oplus b \oplus b = a , a\oplus b = b\oplus a$ 。所以异或两个相同的值时等同于没有异或。所以，树上的简单路径的异或值其实可以看做 $dis_i\oplus dis_j = ans_{i,j}$ 。 $dis_i$ 表示节点 $i$ 到根的异或和。因为 $dis_{lca}$ 的值计算了两次，相当于是抵消了。那么题目转化为，在一个序列上找两个节点使他们的异或值最大。显然这个过程需要优化。我们可以考虑 $\text{01 Trie}$ 。我们按位由大到小建树。这一类的 $\text{01 Trie}$ 有个非常好的性质。在父亲节点就可以知道数的大小关系。这个性质还是比较显然，因为我们是按位由高到低考虑的，那么这一位是 $1$ 的数，一定大于这一位是 $0$ 的数。有了这样优美的性质， $\text{01 Trie}$ 就可以维护一些关于值域的题了。所以直接贪心作就好了。时间复杂度为 $O(n\log n)$ 。

关于01字典树

01 Trie

这个应该是 $\text{Trie}$ 最常见的形态了。一般的 $\text{01 Trie}$ 有按位考虑从高到低的，也有从低到高的。使用方法和处理的问题都有较大的区别。

按位从高到低建树

这一类的 $\text{01 Trie}$ 有个非常好的性质。

在父亲节点就可以知道数的大小关系。

这个性质还是比较显然，因为我们是按位由高到低考虑的，那么这一位是 $1$ 的数，一定大于这一位是 $0$ 的数。有了这样优美的性质， $\text{01 Trie}$ 就可以维护一些关于值域的题了。

一个数字是否出现过

不要跟我说什么 $\text{STL,开个桶,Hash..}$ 。就考虑用 $\text{01 Trie}$ 来考虑这个问题。我们从空节点 $t_0$ 开始，按位转移。如果结束节点是被标记过了的，那么表示出现过，则否。时间复杂度为 $O(\log w)$ 。其实这个从低到高的建的 $\text{Trie}$ 也可以维护，但是放在这里显得更自然。

维护整个序列的第 k 小

这个问题解决有非常多的解决方案，这里也不详细展开了。用 $\text{Trie}$ 来考虑，记录每个节点可以到达的结束节点的个数，记录为 $\text{size}$ 。那么这个 $\text{Trie}$ 树的用法和权值线段树的用法基本也就一模一样了。考虑走左边还是走右边， $\text{k}$ 与 $\text{size}$ 分类讨论就行了，比起权值线段树可以免去离散化的过程，但空间开销要大一点了。

可持久化改造

既然 $\text{01 Trie}$ 有，类似权值线段树的功能。那么如果可以把 $\text{01 Trie}$ 可以持久化，或者用树套一下。权值线段树可以解决的 $\text{01 Trie}$ 也可以解决。

考虑什么时候会新建节点，这个只有在插入的时候才会新建节点。那么也只需要，在这个时候再复制节点就可以了。

异或极值

这里讨论最大值。一个数和一个序列中一个数的异或最大值是多少？要支持询问和修改。

朴素的单次处理需要 $O(n)$ 的复杂度，和 $O(1)$ 的修改。还是考虑平摊一下时间复杂度。
考虑把序列插入，构建一个 $\text{Trie}$ 树。那么在询问时，只需要讨论该数的位是 $0$ 还是 $1$ 就行了。这样就需要 $O(n\log w)$ 的预处理， $O(\log w)$ 的询问和修改。

按位从到高位建树

这个按位从低到高的建树，也有一个很棒的性质，非常好维护异或和。

每一个节点保存该 $\text{Trie}$ 树的异或和。那么在父亲信息合并时。就可以很自然的写出这样的代码，要记住 $\text{Trie}$ 的最后一层其实是没有信息的，所以要把位数限制开高一点。

序列权值+1

今年的省选就考了这样一道题。 $[省选联考 2020 A 卷] 树$ 除开合并儿子信息，那么需要维护一下序列权值 $+1$ 的操作。按 $\text{oi-wiki}$ 的奇妙做法，只需要 $\text{swap(左右儿子)}$ ，其实这个还是比较好理解的。对于每个数的操作，我们都是要从低到高找到第一个不为 $1$ 的位置。然后把这一位改成 $1$ ，后面的全部改为 $0$ 。那么只需要这样递归处理就行了。

Trie 合并

由上一道题延伸出来的知识点，其实适用于所有 $\text{Trie}$ 树。操作方法也比较简单，类似于线段树合并。

代码

#include<bits/stdc++.h>
using namespace std;
const int M = 1000011,N = 1e5 + 10;
int read(){
    int x;scanf("%d",&x);return x;
}
vector<int> G[N],W[N];
int n,dis[N],ch[M][2],size,val[M];
void Dfs(int x,int fa){
    for(int i = 0;i < G[x].size();i++)
    {
        int y = G[x][i];
        if(y == fa) continue;
        dis[y] = dis[x] ^ W[x][i];
        Dfs(y,x);
    }
}
void Insert(int x)
{
    int u = 0;
    for(int i = 30;i >= 0;i--)
    {
        int v = (x>>i)&1;
        if(!ch[u][v]){
            ch[u][v] = ++size;
        }
        u = ch[u][v];
    }
    val[u] = x;
}
int AskXor(int x)
{
    int u = 0;
    for(int i = 30;i >= 0;i--)
    {
        int v = (x>>i)&1;
        if(ch[u][v^1]) u = ch[u][v^1];
        else u = ch[u][v];
    }
    return val[u];
}
int main()
{
    n = read();
    for(int i = 1;i < n;i++)
    {
        int a = read(),b = read(),c = read();
        G[a].push_back(b);W[a].push_back(c);
        G[b].push_back(a);W[b].push_back(c);
    }
    Dfs(1,0);
    int Ans = 0;
    for(int i = 1;i < n;i++) Insert(dis[i]);
    for(int i = 1;i <= n;i++) Ans = max(Ans,dis[i] ^ AskXor(dis[i]));
    printf("%d\n",Ans);

}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！