[CSU - 1811 (湖南省赛16)] Tree Intersection (启发式合并)

2024-06-21 19:38

本文主要是介绍[CSU - 1811 (湖南省赛16)] Tree Intersection (启发式合并),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

CSU - 1811 (湖南省赛16)

给定一棵树,每个节点都有一个颜色
问割掉任意一条边,生成的两个子树中颜色集合的交集大小


问题可以转化为任意一棵子树中,
这个子树中的颜色数量和只在这个子树中出现的颜色的数量
用总的颜色数量减去独有颜色数量即为这棵子树的答案

从 lcy大爷那里学到了机智的启发式合并的做法
对每个点维护一个 map
来记录这个点为根的子树中颜色的及其数量
然后dfs一遍,对每个节点启发式地将其儿子的map合并到父亲上
合并的时候,如果发现一个颜色出现次数用完了
说明它只在这个子树中出现,所以 res++
最后一个节点 u 连向父亲边的答案即为 map[u].size()-res
注意儿子中的 res 要累加到父亲上,
并且统计的时候要记一个 vis,免得算重了

由于采用了启发式合并,所以总的时间复杂度只有 (nlog2(n))
由于每次都最多只有一个 map,所以总的空间复杂度是 (n)
虽然还有时间 (nlogn) 的做法,但我觉得能过就行
况且启发式合并编码复杂度极低,并且具有很好的推广性
从某些角度甚至优于 (nlogn) 的做法

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define SQR(a) ((a)*(a))
#define PCUT puts("\n----------")const int maxn=1e5+10;
struct Graph
{int ndn,edn,last[maxn];int u[2*maxn], v[2*maxn], nxt[2*maxn];void init(int _n){ndn=_n; edn=0; MST(last,-1);}void adde(int _u, int _v){u[edn]=_u; v[edn]=_v;nxt[edn]=last[_u];last[_u]=edn++;}
};int N;
int col[maxn], cnt[maxn], id[maxn], ans[maxn], vis[maxn];
map<int,int> have[maxn];
Graph G;int dfs(int,int);int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);#endifwhile(~scanf("%d", &N)){G.init(N); CLR(cnt); CLR(vis);for(int i=1; i<=N; i++) scanf("%d", &col[i]), cnt[col[i]]++;for(int i=0,u,v; i<N-1; i++){scanf("%d%d", &u, &v);G.adde(u,v); G.adde(v,u);}id[1]=-1;dfs(1,0);for(int i=0; i<N-1; i++) printf("%d\n", ans[i]);}return 0;
}int dfs(int u, int f)
{int res=0;have[u].clear();for(int e=G.last[u],v; ~e; e=G.nxt[e]) if((v=G.v[e])!=f){id[v] = e>>1;res += dfs(v,u);if(have[u].size()<have[v].size()) swap(have[u], have[v]);for(auto &pr:have[v]){have[u][pr.first] += pr.second;if(have[u][pr.first] == cnt[pr.first] && !vis[pr.first]){res++;vis[pr.first] = 1;}}have[v].clear();}have[u][col[u]] ++;if(have[u][col[u]] == cnt[col[u]] && !vis[col[u]]){res++;vis[col[u]] = 1;}if(~id[u]) ans[id[u]] = have[u].size() - res;return res;
}

这篇关于[CSU - 1811 (湖南省赛16)] Tree Intersection (启发式合并)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1082145

相关文章

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col

Python视频剪辑合并操作的实现示例

《Python视频剪辑合并操作的实现示例》很多人在创作视频时都需要进行剪辑,本文主要介绍了Python视频剪辑合并操作的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录介绍安装FFmpegWindowsMACOS安装MoviePy剪切视频合并视频转换视频结论介绍

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map