这是一道很巧妙的题目。
今早，我调了好久，终于将它切掉了……
题目
Description
Input
第一行包含一个正整数 m，代表操作数。
接下来 m 行，每行可能有以下形式：
1 s 代表将数字串 s 加入信息集中
2 s 代表询问数字串 s 是否在信息集中
3 a b 代表使数字串 a 和 b 互相纠缠Output
对于每一个 2 操作，如果询问串不在集合中，请输出一行一个整数 0，否则输出一行一个整 数 1。
Sample Input
11
1 123
2 123
2 0
3 12 13
1 124
2 133
2 134
2 13
3 1 11
2 111
2 11111111111111111111111124Sample Output
1
0
1
1
0
0
1Data constraint
题目大意是这样的：
维护一个数字串集合，每一次有三个操作：
1. 插入一个数字串。
2. 询问一个数字串是否在集合中。
3. 纠缠两个数字串（不一定在这些数字串之内），假设这两个数字串分别为和，插入一些数字串，使得对于任意集合中的，都有也在集合中；对于任意集合中的，都有在集合中（有可能纠缠过后会加入无限的数字串）。
解题思路
我才不会告诉你，我一开始看到这题时，没有理解题目大意。我以为这些加入集合的字符串全部合并在了一起，一想到可能要用某些高端的字符串数据结构，我就感到害怕，于是果断地弃掉了这题。
显然，如果只有前两个操作，那么这就是一道裸裸的Trie。
为什么？不知道为什么的同志们，请再次仔细地理解一下题目大意。如果还不知道为什么，就查查Trie到底是个什么东西。说真的，我觉得Trie是一种无师自通的玩意儿。只要你知道Trie是个什么东西，那么前两个操作对于你来说一定不难。
现在的问题是如何搞第三个操作。
既然前两个操作都和Trie建立了联系，那么不妨想想，如何用Trie来解决。
我们在看看所谓“纠缠”的条件。什么是“纠缠”？把Trie上表示和点找出来，设为和。
那么我们是不是可以理解成，和为根的子树，长得一模一样？
可能有些不好想象，感受一下~~~
算了，放张图。
这样可以理解了吗？
就是让以它们为根的子树长得一模一样。
所以有个思路就是，先把和找出来，暴力地同化它们的子树。
诶~等等，似乎会超时。
读者：你在逗我？
暴力同化它们的子树，这是不现实的。不仅暴力同化花很多时间空间，而且在以后，当有节点插入时，还要在搞，比蜗牛还慢……
与其这样，不如合并和。这样子，下面的就变得一模一样。当后面有插入时，那也可以直接修改，反正两个已经合为一体了。
这个方法非常神奇。显然，它也是正确的。
可能你们会有一堆问题吧，比如，如何合并？
先将和找出来，然后合并。再递归它们的儿子，分别合并。（用并查集）
这样的时间复杂度是不会炸的。建Trie所需要的节点是有限的。在没合并之前，它们就是互相独立的块。每次的合并，将会减少一个块。下次再访问它们时，它们已经是一体的了。
无限的情况怎么办？
其实无限的情况是没必要特判的。相信聪明的读者已经发现了，实际上，出现无限的情况，也就是在合并的时候一个节点和它的祖先合并。那么这些Trie上的转移边，实际上就变成了一个有向图。查询的时候，就像以前那样查询就行了。
一棵好好的Trie树，经过各种合并后，形成了一个有向图……是不是很神奇呢？
算法流程
前面的两个操作就不说了，直接将第三个操作的核心——合并。
假设现在要合并以和为根的子树。
首先，将和各自跳到。
如果则退出。
将所在的集合，并入所在的集合中。用尝试更新上的。（表示这个节点是否有字符串）
然后，枚举它们的儿子。
1. 如果和都没有儿子，不理它们。
2. 如果有儿子，而没有儿子，那么，将的这个转移边连过去。
3. 如果没有儿子，有儿子，不理它们（因为是用合并到中）。
4. 如果两个都有儿子，那么递归合并它们的儿子，合并完后，跳到它的（这一条很玄学，某大佬的解释是：有可能合并完它们的儿子之后，会对已经和同一个并查集中的节点有影响，因为在各种合并之后，这不再是一棵树，而是有向图）。
代码
千言万语不如一标程。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
struct Trie
{
int c[10];//转移边
bool have;//表示这点表示的字符串是否存在于集合之中
int n;//这个节点所在的并查集编号
int num(); //num()就相当于平常打的getfather。在后面使用这些节点时，都是用它们的getfather()，可以看做一个编号。
} d[10000000];
int null,cnt,root;
int Trie::num() {if (&d[n]==this) return n;return n=d[n].num();}
int newnode() {++cnt;d[cnt].n=cnt;return cnt;}
void insert(char *s)
{
int t=root;
for (;*s!=' ';++s)
{
if (!d[t].c[*s-'0'])
d[t].c[*s-'0']=newnode();
t=d[d[t].c[*s-'0']].num();
}
d[t].have=1;
}
bool find(char *s)
{
int t=root;
for (;*s!=' ';++s)
{
if (!d[t].c[*s-'0'])
return 0;
t=d[d[t].c[*s-'0']].num();
}
return d[t].have;
}
int open(char *s)//在Trie中开辟出数字串s。
{
int t=root;
for (;*s!=' ';++s)
{
if (!d[t].c[*s-'0'])
d[t].c[*s-'0']=newnode();
t=d[d[t].c[*s-'0']].num();
}
return t;
}
void merge(int t1,int t2)
{
//这里就不用getfather()了，因为在之前我们已经能够保证它们在并查集中一定是最高的
if (t1==t2)
return;
d[t1].n=t2;//合并
d[t2].have|=d[t1].have;//试着更新have
for (int i=0;i<10;++i)
{
int son1=d[d[t1].c[i]].num(),son2=d[d[t2].c[i]].num();
if (son1)
{
if (!son2)
d[t2].c[i]=son1;//如果t1有儿子,t2没儿子，就将转移边连过来。
else
{
merge(son1,son2);//递归合并
t2=d[t2].num();//试着更新t2，因为下面的合并有可能影响到t2
}
}
}
}
char str1[8000001],str2[100];
int main()
{
freopen("quantum.in","r",stdin);
freopen("quantum.out","w",stdout);
null=0;
root=newnode();
int T;
scanf("%d",&T);
while (T--)
{
int op;
scanf("%d",&op);
if (op==1)
{
scanf("%s",str1);
insert(str1);
}
else if (op==2)
{
scanf("%s",str1);
printf("%d
",find(str1));
}
else
{
scanf("%s %s",str1,str2);
merge(open(str1),open(str2));
}
}
return 0;
}总结
这题真的很神奇。
一个好好的Trie，因为各种奇奇怪怪的合并操作将树压成了一个无向图。
注意，上面的t2=d[t2].num();这一句话非常的玄学，不好理解，要特别注意。这就是60分和100分的差距。