首页 > 其他分享 >树上启发式合并——dsu on tree

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

时间：2024-08-25 16:03:42浏览次数：5  
标签：sz 颜色 int hs dsu tree dfs 集合 启发式

参考文章：

树上启发式合并
[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 \leq n, m \leq 10^5\)，\(1 \leq a_i ,x, y \leq 10^6\)。

提示

请注意，不保证颜色的编号不大于 \(n\)，也不保证 \(x \neq 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\leq n\leq 2\times10^5\)，\(0\leq k,w_i\leq 10^6\)，\(0\leq u_i,v_i<n\)。

思路：

设\(dep1[u]\)表示\(u\)的深度，\(dep2[u]\)表示\(u\)到根节点的路径长度.对于任意两个点\(u,v\),最近公共祖先为\(p\),他们之间的简单路径值\(dep2[u]+dep2[v]-2×dep2[p]\).考虑启发式合并，对于每一个\(p\),用一个\(map\)，记录每一个路径值到根节点的最短距离\(val\),然后遍历每一个轻儿子\(v\)，是否存在已经记录的结点\(u\)，使得\(dep2[u]=k-dep2[v]+2×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;
}

标签：sz,颜色,int,hs,dsu,tree,dfs,集合,启发式
From： https://www.cnblogs.com/prioritymygirl/p/18379048

相关文章

  • 【scikit-opt】七大启发式算法的使用
    @目录前言1.测试函数1.1针状函数1.1.1表达式1.1.2特征1.1.3图像1.2Brains’srcos函数1.2.1表达式1.2.2特征1.2.3图像1.3Griewank函数1.3.1表达式1.3.2特征1.3.3图像1.4Easom’s函数1.4.1表达式1.4.2特征1.4.3图像1.5Schwefel’s函数1.5.1表达式1.5.2特征1.5.3......
  • Infor CloudSuite软件二次开发：InforCloudSuite业务流程定制
    InforCloudSuite软件二次开发：InforCloudSuite业务流程定制InforCloudSuite简介InforCloudSuite平台概述InforCloudSuite是一个集成的企业资源规划(ERP)解决方案，专为特定行业设计，提供了一系列的云应用，旨在优化业务流程，提升运营效率。该平台融合了先进的技术，如人工智......
  • ABC 368D Minimum Steiner Tree
    题意给你一颗由N个点组成的树，指定K个节点，求包含这K个节点的最小子树的大小思路考虑正难则反，我们从开始的树当中剪掉那些没有任何指定点的子树，剩下来的子树就是最小的、能包含所有指定节点的子树。关于剪去这个操作，就是dfs一旦遇到以当前节点为根的子树没有任何指定点时，就停止df......
  • CodeForces-431C k-Tree
    感觉这个题的dp还是有点思维的，可能就是我现在能做到的题目的天花板级别的了，dp还是要点灵感感觉，以下是代码，可能要写题解要过好久，先水着include<bits/stdc++.h>defineintlonglongdefineendl'\n'usingnamespacestd;constintmod=1000000007;intn,k,d;intdp[200][2]=......
  • TreeMap&TreeSet解析
    TreeMapTreeSet使用适配器模式包装了TreeMap，所以只需要理解TreeMap就够了概述TreeMap实现了SortedMap接口，也就是说会按照顺序对Map中的元素进行排序，可以是自然顺序，也可以使用自定义比较器TreeMap<Integer,String>treeMap=newTreeMap<>();treeMap.put(3,"Apple");tree......
  • 数据结构之树(Tree)（一）
    数据结构之树（Tree）（一）文章目录数据结构之树（Tree）（一）一、什么是树？1、有关树的基本概念和术语2、树的类型（二叉树）二、二叉树的实现1、构建一个二叉树节点2、插入（Insert）操作3、搜索（Search）操作一、什么是树？在计算机科学中，树是一种常用的数据结构，用来模拟具有层次关系的数......
  • 金蝶云星空元数据冲突SVN:replaced,tree conflict树冲突解决过程
    问题截图： 解决方式：      ......
  • Tree组件的快速定位更新节点的状态,以及修改节点的数据属性等操作
    当我们点击树节点的时候我们常常只能获得树的id，那么我么如何获快速定位到树节点的内容呢，除此之外，当树已经存在时，但是缺少我们想要的内容时，我们想在树节点上添加我们需要的额外的内容时该怎么办，那么就是用以下方法可以快速定位到我们需要的节点并可以快速添加内容/***@params*......
  • el-tree封装。可以搜索/下拉/高亮/能操作增删改查
    项目场景：     el-tree树形图组写成一个组件，并控制默认高亮问题描述     el-tree树形图组写成一个组件，并控制默认高亮。上边存在搜索框和下拉框。能添加和删除解决方案：组件代码：<template><divclass="grid-contentbg-purple"><!--标题--><......
  • ZoneTree: 高性能ACID兼容的.NET有序键值数据库
    安装Install-PackageZoneTree简单示例usingvarzoneTree=newZoneTreeFactory<int,string>().OpenOrCreate();zoneTree.Upsert(39,"HelloZoneTree");配置示例//设置数据库的存储路径vardataPath="data/mydatabase";//使用using语句确保ZoneTre......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99