北京seoqq群,西安优化外包,鞍山网络,免费制作简历DSU ON TREE
DSU#xff1a;并查集 DSU ON TREE#xff1a;树上启发式合并 我也不知道为啥树上并查集就是树上启发式合并
启发式合并的思想是每次把小的往大的合并#xff0c;也就是最大化利用已有的答案#xff08;大的数组不用清空#xff0c;在原基础上加上小的即可并查集 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 ihead[x];i;ie[i].next){int ve[i].to;if (vfa || vmxson[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 needk2*dis[x]-dis[x];if (show.count(need)){int mndepshow[need];int nowansmndepdeep[x]-2*deep[x]; ansmin(ans,nowans);}for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa || vmxson[x]) continue;calc_ans(v,x,x),add(v,x);}//if (!save) del(x,fa);if (!save) show.clear();
}大致这个样子save表示是否要清空桶。先跑轻儿子清空桶。再跑重儿子不清空桶那么这个桶里的东西再回溯到父亲节点时依然保留。同时注意为什么先calc_ans再add是为了避免有两个点在同一棵子树内的情况即 u → l c a → x → l c a → v u\rightarrow lca\rightarrow x\rightarrow lca\rightarrow v u→lca→x→lca→v的情况。在题目里往往这种情况不合法。
例题
洛谷P4149 [IOI2011] Race 题目链接 题目大意给一棵树每条边有权。求一条简单路径权值和等于k且边的数量最小。 思路问题转化为选择点对 ( u , v ) (u,v) (u,v)满足 d i s u d i s v − d i s l c a ( u , v ) k dis_udis_v-dis_{lca(u,v)}k disudisv−dislca(u,v)k最小化 d e e p u d e e p v − d e e p l c a ( u , v ) deep_udeep_v-deep_{lca(u,v)} deepudeepv−deeplca(u,v)考虑处理以 x x x为根的子树的答案不妨设 l c a ( u , v ) x lca(u,v)x lca(u,v)x在dfs到点u时只需要查找 k 2 ∗ d i s x − d i s u k2*dis_x-dis_u k2∗disx−disu的点都可以作为点 v v v移项可得此时考虑需要最小化的值 d e e p u deep_u deepu和 d e e p x deep_x deepx都是已知值所以只需要开一个桶map维护 m a p [ d ] map[d] map[d]表示 d i s d disd disd的点的 d e e p deep deep最小值。 解决了思路剩下的就是实现DSU ON TREE。注意先遍历子树求解再将该子树加入桶。
#includebits/stdc.h
#define pa pairint,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 f1,sum0;char cgetchar();while (!isdigit(c)) {if (c-) f-1;cgetchar();}while (isdigit(c)) {sumsum*10c-0;cgetchar();}return sum*f;
}
const int MAXN200010;
struct edge{int next,to,val;
}e[MAXN*2];
int head[MAXN],cnt;
void addedge(int u,int v,int w)
{e[cnt].nexthead[u];e[cnt].tov;e[cnt].valw;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 ihead[x];i;ie[i].next){int ve[i].to;if (vfa) 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 ihead[x];i;ie[i].next){int ve[i].to;if (vfa) 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 ihead[x];i;ie[i].next){int ve[i].to;if (vfa) continue;add(v,x);}
}
void calc_ans(int x,int fa,int rt)
{int needk2*dis[rt]-dis[x];if (show.count(need)){int mndepshow[need];int nowansmndepdeep[x]-2*deep[rt];ansmin(ans,nowans);}for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa) continue;calc_ans(v,x,rt);}
}
void dfs2(int x,int fa,int save)
{for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa || vmxson[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 needk2*dis[x]-dis[x];if (show.count(need)){int mndepshow[need];int nowansmndepdeep[x]-2*deep[x]; ansmin(ans,nowans);}for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa || vmxson[x]) continue;calc_ans(v,x,x),add(v,x);}//if (!save) del(x,fa);if (!save) show.clear();
}
int main()
{int nread(); kread();for (int i1;in;i){int uread()1,vread()1,wread();addedge(u,v,w);addedge(v,u,w);}deep[1]1;dfs1(1,0);//for (int i1;in;i) coutdeep[i] dis[i] mxson[i]endl;ansINF;dfs2(1,0,0);if (ansINF) cout-1endl;else coutansendl;return 0;
}有一个小细节是要单独计算一下根的答案因为在后面的过程中并没有再次进入重儿子所以会漏掉重儿子到子树树根的这种答案。其他情况都已经在后面的不断加入中包含。
例题
CF 600E Lomsat gelral 题目链接 题目大意一棵树每个点有个颜色求以每个点为根的子树出现最多的颜色的编号之和。 思路朴素的DSU ON TREE开个桶记录就行众数用set维护当出现更大的清空set出现相等的插入set即可。
#includebits/stdc.h
#define pa pairint,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 f1,sum0;char cgetchar();while (!isdigit(c)) {if (c-) f-1;cgetchar();}while (isdigit(c)) {sumsum*10c-0;cgetchar();}return sum*f;
}
const int MAXN100010;
struct edge{int next,to;
}e[MAXN*2];
int head[MAXN],cnt;
void addedge(int u,int v)
{e[cnt].nexthead[u];e[cnt].tov;head[u]cnt;
}
int sz[MAXN],mxson[MAXN],mxsz[MAXN];
void pre_dfs(int x,int fa)
{for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa) 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 ihead[x];i;ie[i].next){int ve[i].to;if (vfa) 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]);nowsumcol[x];}else if (num[col[x]]nowmax){nowsumcol[x];s.insert(col[x]);}for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa) continue;add(v,x);}
}
ll ans[MAXN];
void dfs(int x,int fa,int save)
{for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa || vmxson[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]);nowsumcol[x];}else if (num[col[x]]nowmax){nowsumcol[x];s.insert(col[x]);}for (int ihead[x];i;ie[i].next){int ve[i].to;if (vfa || vmxson[x]) continue;add(v,x);}ans[x]nowsum;if (!save) del(x,fa),nowsum0,s.clear(),nowmax0;
}
int main()
{int nread();for (int i1;in;i) col[i]read();for (int i1;in;i){int uread(),vread();addedge(u,v),addedge(v,u);}pre_dfs(1,0);dfs(1,0,0);for (int i1;in;i) coutans[i] ;coutendl;return 0;
}
