DSU ON TREE

DSU ON TREE

DSU：并查集
DSU ON TREE：树上启发式合并
我也不知道为啥树上并查集就是树上启发式合并

启发式合并的思想是每次把小的往大的合并，也就是最大化利用已有的答案（大的数组不用清空，在原基础上加上小的即可）。转移到树上，“大”显然就是树的重心。

能解决什么样的问题？需要统计子树信息，但是子树的信息不好合并。比如权值是否出现（桶）。所以肯定要留下最大的，也就是树链剖分的重儿子。

考虑两种合并方式（以对子树做桶排序为例，保留重儿子数组）：

• 遍历子树的桶，对应相加，即类似num[x][val]+=num[v][val]，复杂度O(值域)
• 遍历子树，直接num[x][val[v]]++，复杂度O(子树大小)

显然第一种太大了。

同时，显然不能对每个节点开一个桶表示“以x为根的子树的桶”，空间无法接受，所以桶只能留到一维，这就涉及到清空，因为在dfs另一个儿子时前一个子树的影响要清空。所以要尽可能少的减少清空，在dfs时如果最后访问重儿子，那就可以不清空最大的一部分。

void dfs2(int x,int fa,int save)
{
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa || v==mxson[x]) continue;
		dfs2(v,x,0);
	}
	if (mxson[x]) dfs2(mxson[x],x,1);
	if (!show[dis[x]]) show[dis[x]]=deep[x];
	else show[dis[x]]=min(show[dis[x]],deep[x]);
	int need=k+2*dis[x]-dis[x];
	if (show.count(need))
	{
		int mndep=show[need];
		int nowans=mndep+deep[x]-2*deep[x];	
		ans=min(ans,nowans);
	}
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa || v==mxson[x]) continue;
		calc_ans(v,x,x),add(v,x);
	}
	//if (!save) del(x,fa);
	if (!save) show.clear();
}
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

大致这个样子，save表示是否要清空桶。先跑轻儿子，清空桶。再跑重儿子，不清空桶，那么这个桶里的东西再回溯到父亲节点时依然保留。同时注意为什么先calc_ans再add，是为了避免有两个点在同一棵子树内的情况，即$u\to lca\to x\to lca\to v$的情况。在题目里往往这种情况不合法。

例题

洛谷P4149 [IOI2011] Race
题目链接
题目大意：给一棵树，每条边有权。求一条简单路径，权值和等于k，且边的数量最小。
思路：问题转化为选择点对$(u,v)$，满足$di{s}_u+di{s}_v-di{s}_{lca(u,v)}=k$，最小化$dee{p}_u+dee{p}_v-dee{p}_{lca(u,v)}$，考虑处理以$x$为根的子树的答案，不妨设$lca(u,v)=x$，在dfs到点u时，只需要查找$k+2\ast di{s}_x-di{s}_u$的点，都可以作为点$v$（移项可得），此时考虑需要最小化的值，$dee{p}_u$和$dee{p}_x$都是已知值，所以只需要开一个桶（map）维护$map[d]$表示$dis=d$的点的$deep$最小值。
解决了思路，剩下的就是实现DSU ON TREE。注意先遍历子树求解，再将该子树加入桶。

#include
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=200010;
struct edge{
	int next,to,val;
}e[MAXN*2];
int head[MAXN],cnt;
void addedge(int u,int v,int w)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].val=w;
	head[u]=cnt;
}
int sz[MAXN],mxson[MAXN],mxsz[MAXN];
int deep[MAXN],ans,k;
ll dis[MAXN];
void dfs1(int x,int fa)
{
	sz[x]=1;
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		dis[v]=dis[x]+e[i].val;
		deep[v]=deep[x]+1;
		dfs1(v,x);
		sz[x]+=sz[v];
		if (sz[v]>mxsz[x]) mxson[x]=v,mxsz[x]=sz[v];
	}
}
map <ll,int> show;
void del(int x,int fa)
{
	show[dis[x]]=0;
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		del(v,x);
	}
}
void add(int x,int fa)
{
	if (!show.count(dis[x])) show[dis[x]]=deep[x];
	else show[dis[x]]=min(show[dis[x]],deep[x]);
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		add(v,x);
	}
}
void calc_ans(int x,int fa,int rt)
{
	int need=k+2*dis[rt]-dis[x];
	if (show.count(need))
	{
		int mndep=show[need];
		int nowans=mndep+deep[x]-2*deep[rt];
		ans=min(ans,nowans);
	}
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		calc_ans(v,x,rt);
	}
}
void dfs2(int x,int fa,int save)
{
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa || v==mxson[x]) continue;
		dfs2(v,x,0);
	}
	if (mxson[x]) dfs2(mxson[x],x,1);
	if (!show[dis[x]]) show[dis[x]]=deep[x];
	else show[dis[x]]=min(show[dis[x]],deep[x]);
	int need=k+2*dis[x]-dis[x];
	if (show.count(need))
	{
		int mndep=show[need];
		int nowans=mndep+deep[x]-2*deep[x];	
		ans=min(ans,nowans);
	}
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa || v==mxson[x]) continue;
		calc_ans(v,x,x),add(v,x);
	}
	//if (!save) del(x,fa);
	if (!save) show.clear();
}
int main()
{
	int n=read(); k=read();
	for (int i=1;i<n;i++)
	{
		int u=read()+1,v=read()+1,w=read();
		addedge(u,v,w);
		addedge(v,u,w);
	}
	deep[1]=1;
	dfs1(1,0);
	//for (int i=1;i<=n;i++) cout<
	ans=INF;
	dfs2(1,0,0);
	if (ans==INF) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

有一个小细节是要单独计算一下根的答案，因为在后面的过程中并没有再次进入重儿子，所以会漏掉重儿子到子树树根的这种答案。其他情况都已经在后面的不断加入中包含。

例题

CF 600E Lomsat gelral
题目链接
题目大意：一棵树每个点有个颜色，求以每个点为根的子树出现最多的颜色的编号之和。
思路：朴素的DSU ON TREE，开个桶记录就行，众数用set维护，当出现更大的，清空set，出现相等的，插入set即可。

#include
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=100010;
struct edge{
	int next,to;
}e[MAXN*2];
int head[MAXN],cnt;
void addedge(int u,int v)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
int sz[MAXN],mxson[MAXN],mxsz[MAXN];
void pre_dfs(int x,int fa)
{
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		pre_dfs(v,x);
		sz[x]+=sz[v];
		if (sz[v]>mxsz[x]) mxson[x]=v,mxsz[x]=sz[v];
	}
	sz[x]++;
}
set <int> s;
int num[MAXN],nowmax,col[MAXN];
ll nowsum;
void del(int x,int fa)
{
	num[col[x]]--;
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		del(v,x);
	}
}
void add(int x,int fa)
{
	num[col[x]]++;
	if (num[col[x]]>nowmax)
	{
		nowmax++;
		s.clear();
		s.insert(col[x]);
		nowsum=col[x];
	}
	else if (num[col[x]]==nowmax)
	{
		nowsum+=col[x];
		s.insert(col[x]);
	}
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		add(v,x);
	}
}
ll ans[MAXN];
void dfs(int x,int fa,int save)
{
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa || v==mxson[x]) continue;
		dfs(v,x,0);
	}
	if (mxson[x]) dfs(mxson[x],x,1);
		num[col[x]]++;
	if (num[col[x]]>nowmax)
	{
		nowmax++;
		s.clear();
		s.insert(col[x]);
		nowsum=col[x];
	}
	else if (num[col[x]]==nowmax)
	{
		nowsum+=col[x];
		s.insert(col[x]);
	}
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa || v==mxson[x]) continue;
		add(v,x);
	}
	ans[x]=nowsum;
	if (!save) del(x,fa),nowsum=0,s.clear(),nowmax=0;
}
int main()
{
	int n=read();
	for (int i=1;i<=n;i++) col[i]=read();
	for (int i=1;i<n;i++)
	{
		int u=read(),v=read();
		addedge(u,v),addedge(v,u);
	}
	pre_dfs(1,0);
	dfs(1,0,0);
	for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
	cout<<endl;
	return 0;
}
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126