树上启发式合并——dsu on tree

参考文章：

树上启发式合并
[dsu on tree]树上启发式合并总结
树上启发式合并の详解

启发式合并

启发式算法是什么呢？

启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

举个例子，最常见的就是并查集的启发式合并了，代码是这样的：

void merge(int x, int y) {int xx = find(x), yy = find(y);if (size[xx] < size[yy]) swap(xx, yy);fa[yy] = xx;size[xx] += size[yy];
}

在这里，对于两个大小不一样的集合，我们将小的集合合并到大的集合中，而不是将大的集合合并到小的集合中。

为什么呢？这个集合的大小可以认为是集合的高度（在正常情况下），而我们将集合高度小的并到高度大的显然有助于我们找到父亲。

让高度小的树成为高度较大的树的子树，这个优化可以称为启发式合并算法。

[HNOI2009] 梦幻布丁

P3201 [HNOI2009] 梦幻布丁

题目描述

$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。

例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.

输入格式

第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。
接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型：

• 若 $op=1$，则后有两个整数 $x,y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。
• 若 $op=2$，则表示一次询问。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例 #1

样例输入 #1

4 3
1 2 2 1
2
1 2 1
2

样例输出 #1

3
1

提示

样例 1 解释

初始时布丁颜色依次为 $1,2,2,1$，三段颜色分别为 $[1,1],[2,3],[4,4]$。
一次操作后，布丁的颜色变为 $1,1,1,1$，只有 $[1,4]$ 一段颜色。

数据规模与约定

对于全部的测试点，保证 $1\le n,m\le 10^5$，$1\le a_i,x,y\le 10^6$。

提示

请注意，不保证颜色的编号不大于 $n$，也不保证 $x\ne y$，$m$ 不是颜色的编号上限。

思路

在处理颜色布丁集合合并的问题时，我们面临的是一系列颜色布丁集合，每个集合可以看作一个队列。我们需要频繁地合并两个集合，每次合并操作涉及到两个集合 $x$ 和 $y$。如果采用暴力合并方法，每次合并的复杂度最坏为 $O(n)$，其中 $n$ 是所有集合元素的总和。
为了优化这一过程，我们引入了启发式合并的概念。启发式合并的核心思想是每次将较小的集合合并到较大的集合中，这样每次合并的复杂度为 $O(|短的队列|)$。虽然单次合并的复杂度看起来没有显著改善，但通过均摊分析，我们可以得到更好的整体性能。我们使用贡献法来分析均摊复杂度。假设两个集合分别为 $A$ 和 $B$，且 $|A|<|B|$。我们将 $A$ 暴力加入到 $B$ 中，这样 $A$ 中的元素所在的集合大小变成 $|A|+|B|$，即至少变成了原来的两倍。因此，每个元素至多被加入 $\log n$ 次，总的复杂度为 $O(n\log n)$。
在具体实现步骤中，我们首先对每一种颜色使用$vector$存起来。每次修改时，根据启发式合并的方法来暴力合并，然后处理此次合并对答案的影响（答案是不增的）。为了处理颜色映射问题，如果我们把颜色 $1$ 染成颜色 $2$ 并且 $|S_1|>|S_2|$，那么我们应该把颜色 $2$ 加入到颜色 $1$ 的集合。为了处理这种情况，我们只需要记录一下该颜色的集合中实际的颜色即可

代码

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=2e5+3;
const int LOGN=18; 
using i64 = long long;
int n,m,q;
vector<int> pos[10*N];
int ans=0;
void solve()
{cin>>n>>m;vector<int> a(n+2);for(int i=1;i<=n;i++){cin>>a[i];pos[a[i]].push_back(i);} a[0]=a[n+1]=0;for(int i=0;i<=n;i++) ans+=(a[i]!=a[i+1]);//cout<<ans<<endl;while(m--){int op;cin>>op;if(op==2){cout<<ans-1<<endl;continue;}else if(op==1){int x,y;cin>>x>>y;if(x==y) continue;if(pos[x].size()>pos[y].size()) pos[x].swap(pos[y]);auto modify = [&](int p,int col) -> void{ans-=(a[p]!=a[p-1])+(a[p]!=a[p+1]);a[p]=col;ans+=(a[p]!=a[p-1])+(a[p]!=a[p+1]);};if(pos[y].empty()) continue;int col=a[pos[y][0]];for(auto p : pos[x]){modify(p,col);pos[y].push_back(p);}pos[x].clear();//cout<<ans-1<<endl;}}}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T;T=1;//cin>>T;while(T--){solve();}return 0;
} 

树上启发式合并

遍历节点 u 的步骤

在遍历节点 u 时，我们按照以下步骤进行操作：

1. 遍历轻儿子并计算答案：

   • 首先遍历节点 u 的轻（非重）儿子。
   • 计算这些轻儿子的答案，但不保留它们对 cnt 数组的影响。

2. 遍历重儿子并保留影响：

   • 接着遍历节点 u 的重儿子。
   • 计算重儿子的答案，并保留它对 cnt 数组的影响。

3. 再次遍历轻儿子的子树结点：

   • 最后，再次遍历节点 u 的轻儿子的子树结点。
   • 加入这些结点的贡献，以得到节点 u 的最终答案。

通过这种方式，我们可以有效地计算节点 u 的答案，同时确保重儿子的贡献被保留，轻儿子的贡献在需要时可以重新计算。

int n,m;
int c[N];
int l[N],r[N],id[N],sz[N],hs[N],tot;
vector<int> e[N];
int cnt[N]; //每一个颜色出现次数
int maxcnt; //众数出现次数
int sumcnt,ans[N]; //众数出现的和
void dfs_init(int u,int f)
{l[u] = ++tot;id[tot] = u;sz[u] = 1;hs[u] = -1;for(auto v : e[u]){if(v==f) continue;dfs_init(v,u);sz[u] += sz[v];if(hs[u] == -1 || sz[v] > sz[hs[u]]) hs[u] = v;}r[u] = tot;
}
void dfs_solve(int u,int f,bool keep)
{for(auto v : e[u]){if(v != f && v != hs[u]){dfs_solve(v,u,false);}}if(hs[u] != -1){dfs_solve(hs[u],u,true);//重儿子集合}auto add = [&](int x){};auto del = [&](int x){};for(auto v : e[u]){if(v!=f && v != hs[u]){  //v是轻儿子// 把v子树里所有点加入到重儿子集合中for(int x=l[v];x<=r[v];x++)add(id[x]);}}add(u);ans[u]=sumcnt;//把u 本身加入if(!keep){//清空for(int x=l[u];x<=r[u];x++){del(id[x]);}}
}

题目——模板

E. Lomsat gelral

给你一棵有根的树，根位于顶点 1 。每个顶点都涂有某种颜色。
如果在顶点 v 的子树中，没有其他颜色比颜色 c 出现的次数更多，那么我们就称颜色 c 在顶点 v 的子树中占主导地位。因此，在某个顶点的子树中，可能会有两种或两种以上的颜色占主导地位。
顶点 v 的子树是顶点 v 和其他所有包含顶点 v 的顶点。
对于每个顶点 v 求顶点 v 的子树中所有支配色的总和。

代码：

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;const int N = 3e5+10;
using i64 = long long;int n,m;
int c[N];
int l[N],r[N],id[N],sz[N],hs[N],tot;
vector<int> e[N];
int cnt[N]; //每一个颜色出现次数
int maxcnt; //众数出现次数
int sumcnt,ans[N]; //众数出现的和
void dfs_init(int u,int f)
{l[u] = ++tot;id[tot] = u;sz[u] = 1;hs[u] = -1;for(auto v : e[u]){if(v==f) continue;dfs_init(v,u);sz[u] += sz[v];if(hs[u] == -1 || sz[v] > sz[hs[u]]) hs[u] = v;}r[u] = tot;
}
void dfs_solve(int u,int f,bool keep)
{for(auto v : e[u]){if(v != f && v != hs[u]){dfs_solve(v,u,false);}}if(hs[u] != -1){dfs_solve(hs[u],u,true);//重儿子集合}auto add = [&](int x){x=c[x];cnt[x]++;if(cnt[x] > maxcnt) maxcnt=cnt[x],sumcnt=0;if(cnt[x] == maxcnt) sumcnt+=x;};auto del = [&](int x){x=c[x];cnt[x]--;};for(auto v : e[u]){if(v!=f && v != hs[u]){  //v是轻儿子// 把v子树里所有点加入到重儿子集合中for(int x=l[v];x<=r[v];x++)add(id[x]);}}add(u);ans[u]=sumcnt;//把u 本身加入if(!keep){//清空maxcnt=0;sumcnt=0;for(int x=l[u];x<=r[u];x++){del(id[x]);}}
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>c[i];for(int i=1;i<n;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs_init(1,0);dfs_solve(1,0,0);for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
}

[IOI2011] Race

P4149 [IOI2011] Race

题目描述

给一棵树，每条边有权。求一条简单路径，权值和等于 $k$，且边的数量最小。

输入格式

第一行包含两个整数 $n,k$，表示树的大小与要求找到的路径的边权和。

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，代表有一条连接 $u_i$ 与 $v_i$，边权为 $w_i$ 的无向边。

注意：点从 $0$ 开始编号。

输出格式

输出一个整数，表示最小边数量。

如果不存在这样的路径，输出 $-1$。

样例 #1

样例输入 #1

4 3
0 1 1
1 2 2
1 3 4

样例输出 #1

2

提示

对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$0\le k,w_i\le 10^6$，$0\le u_i,v_i<n$。

思路：

设$dep1[u]$表示$u$的深度，$dep2[u]$表示$u$到根节点的路径长度.对于任意两个点$u,v$,最近公共祖先为$p$,他们之间的简单路径值$dep2[u]+dep2[v]-2\times dep2[p]$.考虑启发式合并，对于每一个$p$,用一个$map$，记录每一个路径值到根节点的最短距离$val$,然后遍历每一个轻儿子$v$，是否存在已经记录的结点$u$，使得$dep2[u]=k-dep2[v]+2\times dep2[u]$,然后将轻儿子加入到重儿子集合中。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m,k,q;
vector<PII> e[N];
int dep1[N],dep2[N];
int l[N],r[N],dfn[N],hs[N],sz[N],tot;
int ans;
map<int,int> val;
void dfs_init(int u,int f)
{l[u]=++tot;hs[u]=-1;sz[u]=1;dfn[tot]=u;//cout<<u<<endl;for(auto [v,w] : e[u]){if(v==f) continue;dep1[v]=dep1[u]+1;dep2[v]=dep2[u]+w;dfs_init(v,u);sz[u]+=sz[v];if(hs[u] == -1 || sz[hs[u]] < sz[v]) hs[u]=v;}r[u]=tot;
}
void dfs_solve(int u,int f,int keep)
{//cout<<hs[u]<<endl;for(auto [v,w] : e[u]){if(v!=hs[u]&&v!=f) dfs_solve(v,u,0);}if(hs[u]!=-1) dfs_solve(hs[u],u,1);auto query = [&](int w){int d2=k+2*dep2[u]-dep2[w];if(val.count(d2))ans=min(ans,val[d2]+dep1[w]-2*dep1[u]);};auto add = [&](int w){if(val.count(dep2[w]))val[dep2[w]]=min(val[dep2[w]],dep1[w]);else val[dep2[w]]=dep1[w];};for(auto [v,w] : e[u]){if(v==f||v==hs[u]) continue;for(int x=l[v];x<=r[v];x++)query(dfn[x]);for(int x=l[v];x<=r[v];x++)add(dfn[x]);}query(u);add(u);if(!keep){val.clear();}
}
void solve()
{cin>>n>>k;for(int i=1;i<n;i++){int u,v,w;   cin>>u>>v>>w;++u,++v;e[u].push_back({v,w});e[v].push_back({u,w});}ans=n+1;dfs_init(1,0);dfs_solve(1,0,0);if(ans<n+1) cout<<ans<<endl;else cout<<"-1"<<endl;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);T=1;//cin>>T;while(T--){solve();}return 0;
}