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();
}

大致这个样子，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<bits/stdc++.h>
#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_backusing 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<<deep[i]<<' '<<dis[i]<<' '<<mxson[i]<<endl;ans=INF;dfs2(1,0,0);if (ans==INF) cout<<-1<<endl;else cout<<ans<<endl;return 0;
}

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

例题

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

#include<bits/stdc++.h>
#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_backusing 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;
}