写 P6623 [省选联考 2020 A 卷] 树 时发现根本不会，强制恶补。
如有不足，还请提出。
1.是什么
请出老朋友并查集，并查集中有个优化为按两个并查集高度大小贪心的合并。
1
2
3
4
5
6
7
| void merge(int x,int y)
{
int fax=find(x),fay=find(y);
if(siz[fax]<siz[fay])swap(fax,fay);
fa[fay]=fax,siz[fax]+=siz[fay];
return ;
}l
|
恭喜你，学会了启发式合并
当然，启发式合并还有其他用处，我大致理解为对于树上的子树问题，假如每次询问可以用 $O(n)$ 解决并且离线，那么就能尝试把启发式合并套上去。
怎么写
以下面这道题为例：
给出一棵 $n$ 个节点以 $1$ 为根的树，节点 $u$ 的颜色为 $c_u$，现在对于每个结点 $u$ 询问以 $u$ 为根的子树里一共出现了多少种不同的颜色。
离线下来，对于每次询问，显然是可以 O(n) 遍历一遍，用桶记录颜色的。但是我们发现，如果遍历的过程中有很多重复的过程，能不能像并查集合并那样将当前的答案从儿子那转移过来呢。
如果你不考虑空间，可以每次都保留每棵子树对应的桶，但这显然会炸。我们只保留一个桶，则保留子树大小最大（重儿子）的桶是最优的，则对于轻儿子我们仍然用相同的办法统计答案（递归下去）。
在遍历完之后将轻儿子的桶清空，避免影响重儿子以及其他儿子的答案统计，最后遍历重儿子，统计答案并且不清空桶。
此时对于当前节点，我们已经有了重儿子的答案（桶），直接拿过来用就好了。接下来只用再遍历一遍轻儿子，将答案加入桶内即可。
实现
给个大致代码，随意口胡的，喷轻点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void add(int x){}
void add(int x){}
void del(int x){}
int root;
void update(int x,int fa,int flag)
{
if(flag)add(x);
else del(x);
for(auto y:a[x])
if(y!=fa&&y!=son[root])
update(y,x,flag);
return ;
}
void dfs(int x,int fa,int flag)
{
for(auto y:a[x])
if(y!=fa&&y!=son[x])
dfs(y,x,0);
if(son[x])dfs(son[x],x,1);
root=x;
update(x,fa,1);
if(!flag)update(x,fa,0);
return ;
}
|
时间复杂度不太会证，反正这种可以 $O(n)$ 求一个子树答案的基本上都是 $O(n log n)$。(也许？
例题
就开头那道吧，P6623 [省选联考 2020 A 卷] 树。
01 Trie 经典存异或值贪心统计答案，一个 $val(i)$ 是好求的，直接用 $dsu on tree$ 优化，最后将答案累加就完了。
Tips: 01 Trie 的一个 Trick，快速整体加一之若存在 1 儿子，则交换左右子树，要求从低到高位存 Trie。具体画图感性理解吧。作者太菜
细节看注释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=525015;
int n;
int v[N];
vector<int>ed[N];
int son[N],deep[N],siz[N];
int Ans[N],root;
namespace Trie{
int tr[N*20][2],s[30][2],siz[N*20],tot=1;
void insert(int x)
{
int pos=1;
for(int i=0;i<=20;i++)
{
siz[pos]++;
bool op=x&(1<<i);
if(!tr[pos][op])tr[pos][op]=++tot;
s[i][op]++,pos=tr[pos][op];
}
siz[pos]++;
return ;
}
int query()
{
int ans=0;
for(int i=20;i>=0;i--)
if(s[i][1]&1)ans+=(1<<i);
return ans;
}
void update()
{
int pos=1;
for(int i=0;i<=20;i++)
{
int l=siz[tr[pos][0]],r=siz[tr[pos][1]];
s[i][0]+=r-l,s[i][1]+=l-r;
swap(tr[pos][0],tr[pos][1]),pos=tr[pos][0];
if(!pos)return ;
}
return ;
}
void clear()
{
for(int i=1;i<=tot;i++)siz[i]=tr[i][0]=tr[i][1]=0;
memset(s,0,sizeof(s));
tot=1;
return ;
}
}
void dfs(int x)
{
siz[x]=1;
for(auto y:ed[x])
deep[y]=deep[x]+1,dfs(y),siz[x]+=siz[y],
son[x]=siz[son[x]]<siz[y]?y:son[x];
return ;
}
void update(int x)
{
Trie::insert(v[x]+deep[x]-deep[root]);
for(auto y:ed[x])
if(y!=son[root])
update(y);
return ;
}
void dfs1(int x,int flag)
{
for(auto y:ed[x])
if(y!=son[x])
dfs1(y,0);
if(son[x])dfs1(son[x],1),Trie::update();
root=x;
update(x),Ans[x]=Trie::query();
if(!flag)Trie::clear();
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
cin>>n;
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=2,x;i<=n;i++)
cin>>x,ed[x].push_back(i);
dfs(1),dfs1(1,1);
int ans=0;
for(int i=1;i<=n;i++)ans+=Ans[i];
cout<<ans;
return 0;
}
|
嗯，不错。剩下的以后写了题再补。
