【树哈希】CF1182D Complete Mirror

CF1182D - Complete Mirror

Description

给定一个 n n n 个点的无根树,求一个树根 r o o t root root,使得对于任意两个节点 v 1 , v 2 v_1,v_2 v1,v2,若满足 d i s t ( v 1 , r o o t ) = d i s t ( v 2 , r o o t ) dist(v_1,root)=dist(v_2,root) dist(v1,root)=dist(v2,root),则必有 d g r ( v 1 ) = d g r ( v 2 ) dgr(v_1)=dgr(v_2) dgr(v1)=dgr(v2),无解输出 − 1 -1 1

d i s t ( u , v ) dist(u,v) dist(u,v)定义为 u , v u,v u,v 之间的边数, d g r ( v ) dgr(v) dgr(v) 定义为与 v v v 点直接相连的点的个数。


Solution

如果以某一个点为根时,树满足如上条件的充分必要条件为在第一个分叉点的所有儿子所构成的子树均为同构的。

例:

如图,第一个分叉点为 3 3 3 号点,所有儿子为 4 , 5 4,5 4,5 号点,显然他们所构成的子树是同构的。

那么,问题变成了如何找出第一个分叉点以及判断子树均同构

子树均同构

树哈希是解决这一类问题最有效的办法,当然树哈希也有好几种,这里小编采取 这一种。

不过,由于该题有换根操作,所以需要考虑如何换根:

d p ( u ) dp(u) dp(u) 表示以 u u u 为根的子树的哈希值,那么 d p ( u ) = ∑ v ∈ s o n ( u ) ( 1 + f ( d p ( v ) ) ) dp(u)=\sum_{v\in son(u)}(1+f(dp(v))) dp(u)=vson(u)(1+f(dp(v)))

对于一棵树:

如果从以 1 1 1 为根换到以 2 2 2 为根,那么哪些子树的哈希值会发生变化呢? 1 1 1 号和 2 2 2 号节点的子树的哈希值会发生变化,其余均不发生任何变化。

考虑 1 1 1 号节点子树哈希值:

  • 原来: d p ( 1 ) = 1 + f ( d p ( 2 ) ) + 1 + f ( d p ( 5 ) ) dp(1)=1+f(dp(2))+1+f(dp(5)) dp(1)=1+f(dp(2))+1+f(dp(5))
  • 现在: d p ( 1 ) = 1 + f ( d p ( 5 ) ) dp(1)=1+f(dp(5)) dp(1)=1+f(dp(5))

故,当 u u u 换根到 v v v 时, d p ( u ) = d p ( u ) − 1 − f ( d p ( v ) ) dp(u)=dp(u)-1-f(dp(v)) dp(u)=dp(u)1f(dp(v))

考虑 2 2 2 号节点子树哈希值:

  • 原来: d p ( 2 ) = 1 + f ( d p ( 3 ) ) + 1 + f ( d p ( 4 ) ) dp(2)=1+f(dp(3))+1+f(dp(4)) dp(2)=1+f(dp(3))+1+f(dp(4))
  • 现在: d p ( 2 ) = 1 + f ( d p ( 3 ) ) + 1 + f ( d p ( 4 ) ) + 1 + f ( d p ( 1 ) ) dp(2)=1+f(dp(3))+1+f(dp(4))+1+f(dp(1)) dp(2)=1+f(dp(3))+1+f(dp(4))+1+f(dp(1)),注意这里的 d p ( 1 ) dp(1) dp(1) 为更改后的 d p dp dp 值。

故,当 u u u 换根到 v v v 时, d p ( v ) = d p ( v ) + 1 + f ( d p ( v ) ) dp(v)=dp(v)+1+f(dp(v)) dp(v)=dp(v)+1+f(dp(v)),注意这里的 d p ( v ) dp(v) dp(v) 为更改后的 d p dp dp 值。

这样,就可以快速判断子树同构了!


第一个分叉点

这个确实不是很好直接干,直接干容易超时,不过转化一下:当以该分叉点为根时会发生什么?

若树为如下所示:

1 1 1 个分叉点为 3 3 3,将 3 3 3 为根时:

可以发现如果以分界点为根时,有 1 1 1 条链以及其余子树均同构,那么把这条链的端点移为根时,那么就是一颗满足条件的树,故这时候输出那条链的端点即可。

其余情况就判断所有儿子的子树是否均同构即可。更多小细节留给大家思考,这里不再赘述。


Code

其中代码前半段为取模板子,删掉后大概 112 112 112 行。

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int MOD = 1e9 + 7;
int ksm(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void exgcd(int a, int b, int &x, int &y) {
	if (!b) {
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b, y, x);
	y -= a / b * x;
}
struct Mint {
	int v;
	void assign(int x) {
		v = x;
	}
	Mint operator+ (const Mint tmp)const {
		Mint res;
		res.v = (v + tmp.v) % MOD;
		return res;
	}
	Mint operator+ (const int tmp)const {
		Mint res;
		res.v = (v + tmp) % MOD;
		return res;
	}
	Mint operator- (const Mint tmp)const {
		Mint res;
		res.v = (v - tmp.v + MOD) % MOD;
		return res;
	}
	Mint operator- (const int tmp)const {
		Mint res;
		res.v = (v - tmp + MOD) % MOD;
		return res;
	}
	Mint operator* (const Mint tmp)const {
		Mint res;
		res.v = v * tmp.v % MOD;
		return res;
	}
	Mint operator* (const int tmp)const {
		Mint res;
		res.v = v * tmp % MOD;
		return res;
	}
	Mint operator/ (const Mint tmp)const {
		int x, y;
		exgcd(tmp.v, MOD, x, y), x = (x % MOD + MOD) % MOD;
		Mint res;
		res.v = v * x % MOD;
		return res;
	}
	Mint operator/ (const int tmp)const {
		int x, y;
		exgcd(tmp, MOD, x, y), x = (x % MOD + MOD) % MOD;
		Mint res;
		res.v = v * x % MOD;
		return res;
	}
	Mint operator^ (Mint b)const {
		Mint ans;
		ans.v = ksm(v, b.v);
		return ans;
	}
	Mint operator^ (int b)const {
		Mint ans;
		ans.v = ksm(v, b);
		return ans;
	}
	void read() {
		string s;
		cin >> s;
		for (auto i : s)
			v = (v * 10 + i - '0') % MOD;
	}
};

const int N = 1e5 + 10;

int n;
std::vector<int> G[N];
Mint dp[N];
int far[N];

Mint h(Mint x) {
	return x * x * x * 1237123 + 1145141;
}
Mint f(Mint x) {
	Mint ok, res;
	res.v = 0;
	ok.v = (x.v & ((1ll << 31) - 1)), res = res + h(ok);
	ok.v = (x.v >> 31), res = res + h(ok);
	return res;
}
Mint dfs1(int u, int fa) {
	for (auto v : G[u]) {
		if (v == fa) continue;
		dp[u] = dp[u] + 1 + f(dfs1(v, u));
	}
	return dp[u];
}
void dfs2(int u, int fa) {
	unordered_map<int, int> cnt;
	int tot = 0;
	for (auto v : G[u]) {
		cnt[dp[v].v] ++, tot ++;
	}
	if (tot >= 3) {
		if (cnt.size() == 2) {
			for (auto v : G[u])
				if (cnt[dp[v].v] == 1 && far[v]) {
					cout << far[v] << endl;
					exit(0);
				}
		}
		if (cnt.size() == 1) {
			cout << u << endl;
			exit(0);
		}
	} else if (tot == 2) {
		if (cnt.size() == 1) {
			cout << u << endl;
			exit(0);
		}
	}

	for (auto v : G[u]) {
		if (v == fa) continue;
		Mint tmp1 = dp[u], tmp2 = dp[v];
		int tf1 = far[v], tf2 = far[u];
		dp[u] = dp[u] - 1 - f(dp[v]), dp[v] = dp[v] + 1 + f(dp[u]);
		if (G[u].size() == 2) {
			if (v == G[u][0] && far[G[u][1]]) far[u] = far[G[u][1]];
			if (v == G[u][1] && far[G[u][0]]) far[u] = far[G[u][0]];
		} else if (G[u].size() == 1) {
			far[u] = u;
		}
		far[v] = 0;
		dfs2(v, u);
		dp[u] = tmp1, dp[v] = tmp2, far[v] = tf1, far[u] = tf2;
	}
}
void dfs3(int u, int fa) {
	int tot = 0, p;
	for (auto v : G[u]) {
		if (v == fa) continue;
		tot ++, p = v;
		dfs3(v, u);
	}
	if (tot == 1) far[u] = far[p];
	if (tot == 0) far[u] = u;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	int u, v, fir = 0;
	for (int i = 1; i < n; i ++) {
		cin >> u >> v, G[u].emplace_back(v), G[v].emplace_back(u);
		if (!fir) fir = u;
	}

	dfs1(1, -1);
	dfs3(1, -1);
	if (far[1] || (G[1].size() == 2 && far[G[1][0]] && far[G[1][1]])) {
		if (far[1]) cout << 1 << endl;
		else cout << far[G[1][0]] << endl;
		return 0;
	}
	dfs2(1, -1);

	cout << -1 << endl;

	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/544656.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CUDA编程---全局内存

CUDA内存模型概述 内存的访问和管理是所有编程语言的重要部分。在现代加速器中&#xff0c;内存管理对高性能计算有着很大的影响。因为多数工作负载被加载和存储数据的速度所限制&#xff0c;所以有大量低延迟、高带宽的内存对性能是十分有利的。 然而&#xff0c;大容量、高性…

第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结

目录 个人总结 C/C 组真题 握手问题 小球反弹 好数 R 格式 宝石组合 数字接龙 爬山 拔河 ​编辑 再总结及后续规划 个人总结 第一次参加蓝桥杯&#xff0c;大二&#xff0c;以前都在在学技术&#xff0c;没有系统的学过算法。所以&#xff0c;还是花了挺多时间去备…

【8086汇编】汇编语言基础入门

文章目录 一、汇编简介1. 汇编语言的组成2. CPU、寄存器、内存3. CPU对存储器的读写4. 拓展5. 检测6. 解析 二、寄存器1. mov、add命令2. 物理地址3. CS:IP 装段地址和偏移地址3.1 如何改变CS:IP的值 4. 数据段DS:[address]4.1 前置知识&#xff1a;字与字节4.2 DS:[address] 5…

串口RS485

1.原理 全双工&#xff1a;在同一时刻可以同时进行数据的接收和数据的发送&#xff0c;两者互不影响 半双工&#xff1a;在同一时刻只能进行数据的接收或者数据的发送&#xff0c;两者不能同时进行 差分信号幅值相同&#xff0c;相位相反&#xff0c;有更强的抗干扰能力。 干…

【C语言】N子棋小游戏♔

目录 前言 一、何为N子棋游戏&#xff1f; 二、游戏思路 三、游戏实现 3.1 模块化 3.2 游戏棋盘 3.3 下棋操作 3.3.1 玩家下棋 3.3.2 电脑下棋 3.4 判断输赢 总结 前言 三子棋小游戏相信大家都玩过吧&#xff0c;类似的5子琪等等&#xff0c;这篇文章将带着大家从0到…

【leetcode面试经典150题】28.盛最多水的容器(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…

分享一些有趣的 Linux 命令

1、sl 会显示一辆火车穿过你的终端屏幕 2、cmatrix 在终端中显示类似于《黑客帝国》电影中的绿色数字雨效果 3、fortune 显示一个随机的名人名言或者笑话 4、cowsay 让一头牛说出你输入的话 5、toilet 在终端中将输入的文本以艺术字体的形式呈现 6、figlet 类似于 toile…

回溯算法初识

文章目录 回溯算法初识什么是回溯算法回溯算法的步骤回溯算模版例题 回溯算法初识 什么是回溯算法 ​ 回溯算法是一种通过不断尝试可能的解决方案来解决问题的算法。它通常用于解决组合优化问题&#xff0c;如排列组合问题、子集和问题等。该算法通过尝试所有可能的候选解&am…

【热门话题】常见分类算法解析

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 常见分类算法解析1. 逻辑回归&#xff08;Logistic Regression&#xff09;2. 朴…

【设计模式】聊聊观察者设计模式原理及应用

原理 观察者模式属于行为模式&#xff0c;行为模式主要解决类和对象之间交互问题。 含义&#xff1a;在对象之间定义一个一对多的依赖&#xff0c;当一个对象状态改变时&#xff0c;所有依赖的对象会自动通知。 被依赖的对象被观察者(Observable) &#xff0c;依赖的对象观察…

移动Web学习06-移动端适配Less预处理器项目案例

项目目标&#xff1a;实现在不同宽度设备中等比缩放的网页效果 Less代码 import ./base; import ./normalize;// 变量: 存储37.5 rootSize: 37.5rem; *{margin: 0;padding: 0; } body {background-color: #F0F0F0; }// 主体内容 .main {// padding-bottom: (50 / 37.5rem);pa…

缺失msvcr110.dll要怎么处理?快捷的修复msvcr110.dll方法

当你在使用电脑进行工作或娱乐时&#xff0c;可能会突然遇到一个错误提示&#xff1a;“程序无法启动&#xff0c;因为电脑中缺失msvcr110.dll”。这样的情况不仅会打断你的活动&#xff0c;还可能带来一定程度的不便。面对这个在Windows操作系统中相对常见的问题&#xff0c;其…

IDEA2023 开发环境配置

目录 1. 关闭IDEA自动更新1.2 IDEA 新版样式切换 2. Maven配置2.1本地仓库优先加载2.2 maven.config配置文件中 3. 全局配置JDK4. 配置文件编码:UTF-85. 开启自动编译&#xff08;全局配置&#xff09;6. 开启自动导包7. 开启鼠标悬浮&#xff08;提示文档信息&#xff09;8. 设…

7 个适用于 Windows 的最佳电脑分区数据恢复软件

磁盘分区对于正确存储数据以便从硬盘驱动器快速轻松地访问非常有帮助。但是&#xff0c;如果分区损坏&#xff0c;存储在其中的所有数据都会突然变得无法访问。磁盘分区损坏的原因可能有很多&#xff0c;其中最突出的是病毒攻击、突然断电、物理损坏或由于创建坏扇区。 但是&a…

gzip,bzip2,xz,tar-读书笔记(九)

gzip 将文件进行压缩 在Linux系统中&#xff0c;gzip 是一个压缩和解压文件的命令工具。它使用LZ77压缩算法及霍夫曼编码&#xff08;Huffman Coding&#xff09;来压缩文件&#xff0c;通常用来减少文件的大小&#xff0c;以节约磁盘空间或减少网络传输的时间。 gzip 命令的…

Linux gcc 6

本章开始学习工具 什么是工具&#xff1f; 本质也是指令 yum 命令 小火车 sudo yum install sl&#xff08;安装sl&#xff09; sudo yum install -y sl //直接yes就不提示了 yum list //将yum源上的软件都穷举出来 yum search sl //结果不友好&#xff0c;不推荐 yum lis…

Python-GEE遥感云大数据分析、管理与可视化及多领域案例实践应用

随着航空、航天、近地空间遥感平台的持续发展&#xff0c;遥感技术近年来取得显著进步。遥感数据的空间、时间、光谱分辨率及数据量均大幅提升&#xff0c;呈现出大数据特征。这为相关研究带来了新机遇&#xff0c;但同时也带来巨大挑战。传统的工作站和服务器已无法满足大区域…

【数据结构】泛型(分享重点)

什么是泛型&#xff1f; 泛型就是适用于许多许多类型&#xff0c;对类型参数化。 怎么创建一个泛型呢 class 泛型类名称<类型形参列表> { // 这里可以使用类型参数 } class ClassName<T1, T2, ..., Tn> { } class 泛型类名称<类型形参列表> extends 继承类…

Hadoop 3.1.3

第1章 Hadoop概述 1.1 Hadoop是什么 1.2 Hadoop发展历史&#xff08;了解&#xff09; 1.3 Hadoop三大发行版本&#xff08;了解&#xff09; Hadoop三大发行版本&#xff1a;Apache、Cloudera、Hortonworks。 Apache版本最原始&#xff08;最基础&#xff09;的版本&#x…

AI大模型探索之路-提升篇2:一文掌握AI大模型的核心-注意力机制

目录 前言 一、注意力机制简介 二、注意力机制的工作原理 三、注意力机制的变体 1、自注意力&#xff08;Self-Attention&#xff09; 2、双向注意力&#xff08;Bidirectional Attention&#xff09; 3、多头注意力&#xff08;Multi-Head Attention&#xff09; ​4、…