点分治及其例题

news/2024/7/9 5:29:10

点分治

处理树上问题，将问题范围分为穿过树根的与子树内部

对于子树内部采用递归处理，对穿过树根具体题目具体分析

为了让递归层数尽量少，先要找重心

找重心：

重心为所有子树的最大值最小的节点

用 s z [ i ] sz[i] sz[i]记录点 i i i作为父亲子树时的子树数量，每次从父节点到 i i i节点时初始化为 1 1 1

用 m a x _ s z [ i ] max\_sz[i] max_sz[i]记录节点最大的子树数量，递归处理完所有子树后，用 a l l − s z [ i ] all-sz[i] all−sz[i]更新 m a x _ s z [ i ] max\_sz[i] max_sz[i]即可得到 i i i节点的最大子树节点数量，再更新 z x zx zx即可

分治：找重心，计算经过重心的可能性，遍历以重心为根的子树，对那些子树找重心继续递归

模板点分治1

#include<bits/stdc++.h>
using namespace std;

const int N = 2e4 + 10,M = 1e2 + 10;
const int INF = 1e7 + 10;

bool vis[N],able[M];
int n,m,zx,idx;
int zs[N],max_zs[N],ask[M];
int d[N],dis[N];
bool judge[INF];

struct edge{
	int v,w;
	edge* nex;
}ed[N*2];
int ptop;
edge* head[N];

void add(int u,int v,int w){
	ed[ptop].v = v;
	ed[ptop].w = w;
	ed[ptop].nex = head[u];
	head[u] = &ed[ptop];
	ptop++;
}

void get(){
	cin >> n >> m;
	for(int i = 1;i <= n - 1;i++){
		int u,v,w;cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w);
	}
	for(int i = 1;i <= m;i++)
		cin >> ask[i];
}

void get_zx(int u,int fa,int all){
	zs[u] = 1;
	max_zs[u] = 0;
	for(edge* p = head[u];p != NULL;p = p -> nex){
		int v = p -> v;
		if(vis[v] || v == fa) continue;
		get_zx(v,u,all);
		zs[u] += zs[v];
		max_zs[u] = max(max_zs[u],zs[v]);
	}
	max_zs[u] = max(all - zs[u],max_zs[u]); 
	if(max_zs[u] < max_zs[zx])
		zx = u;
}

void get_dis(int u,int fa,int len){
	d[++idx] = len;
	for(edge* p = head[u];p != NULL;p = p -> nex){
		int v = p -> v,w = p -> w;
		if(vis[v] || v == fa) continue;
		get_dis(v,u,len + w);
	}
}

void calc(int x){
	judge[0] = 1;
	stack<int> st;
	for(edge* p = head[x];p != NULL;p = p -> nex){//所有子树
		int v = p -> v,w = p -> w;
		if(vis[v]) continue;
		idx = 0;
		get_dis(v,x,w);//这个子树上的所有距离
		for(int i = 1;i <= idx;i++){
			for(int j = 1;j <= m;j++){
				if(ask[j] - d[i] >= 0 && ask[j] - d[i] < INF && judge[ask[j] - d[i]])
					able[j] = 1;
			}
		}
		for(int i = 1;i <= idx;i++)//处理完成，放入judge
		{
			if(d[i] <= INF){
				judge[d[i]] = 1;
				st.push(d[i]);
			}
		}
	}
	while(!st.empty()){//清空judge
		judge[st.top()] = 0;
		st.pop();
	}
}

void divid(int x){
	calc(x);//计算经过x的
	vis[x] = 1;
	for(edge* p = head[x];p != NULL;p = p -> nex){
		int v = p -> v;
		if(vis[v]) continue;
		zx = 0;
		get_zx(v,x,zs[v]);
		divid(zx);
	}
}

int main(){
	ios::sync_with_stdio(false);//写了using namespace std;
	get();
	zx = 0;
	max_zs[0] = INF;
	get_zx(1,0,n);
	divid(zx);
	for(int i = 1;i <= m;i++){
		if(able[i])
			cout << "AYE" << endl;
		else
			cout << "NAY" << endl;
	}
}

聪聪可可

找所有3倍数的连接（包括本身，ab与ba不同）

正常分治，calc时记录0,1,2的数量即可

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2e4 + 10,INF = 1e9 + 10;

ll gcd(ll a,ll b){
	if(b == 0) return a;
	else return gcd(b,a%b);
}

ll n;
bool vis[N];
int zs[N],max_zs[N],zx;

struct edge{
	int v,w;
	edge* nex;
}ed[N*2];
int ptop;
edge* head[N];
void add(int u,int v,int w){
	ed[ptop].v = v;
	ed[ptop].nex = head[u];
	ed[ptop].w = w;
	head[u] = &ed[ptop++];
}

void get_zx(int u,int fa,int all){
	zs[u] = 1;
	max_zs[u] = 0;
	for(edge* p = head[u];p != NULL;p = p -> nex){
		int v = p -> v;
		if(vis[v] || v == fa) continue;
		get_zx(v,u,all);
		zs[u] += zs[v];
		max_zs[u] = max(max_zs[u],zs[v]);
	}
	max_zs[u] = max(max_zs[u],all - zs[u]);
	if(max_zs[zx] > max_zs[u])
		zx = u;
}

ll num[3],d[3],ans;

void get_dis(int u,int fa,int len){
	d[len]++;
	for(edge* p = head[u];p != NULL;p = p -> nex){
		int v = p -> v,w = p -> w;
		if(vis[v] || v == fa) continue;
		get_dis(v,u,(len + w) % 3);
	}
}

void calc(int u){
	num[1] = num[2] = 0;
	num[0] = 1;
	for(edge* p = head[u];p != NULL;p = p -> nex){
		int v = p -> v,w = p -> w;
		if(vis[v]) continue;
		d[0] = d[1] = d[2] = 0;
		get_dis(v,u,w % 3);
		for(int i = 0;i < 3;i++)
			ans += num[(3 - i) % 3]*d[i];
		for(int i = 0;i < 3;i++)
			num[i] += d[i];
	}
}

void divid(int u){
	calc(u);
	vis[u] = 1;
	for(edge* p = head[u];p != NULL;p = p -> nex){
		int v = p -> v;
		if(vis[v]) continue;
		zx = 0;
		get_zx(v,u,zs[v]);
		divid(zx);
	}
}

void get(){
	cin >> n;
	for(int i = 1;i <= n - 1;i++){
		int u,v,w;cin >> u >> v >> w;
		w %= 3;
		add(u,v,w);
		add(v,u,w);
	}
}

int main(){
	max_zs[0] = INF;
	get();
	zx = 0;
	get_zx(1,0,n);
	divid(zx);
	ll all = n*n;
	ans = ans * 2 + n;
	ll gc = gcd(ans,all);
	cout << ans / gc << '/' << all / gc << endl;
}

http://lihuaxi.xjx100.cn/news/1294696.html

相关文章

分享如何安全运营多个eBay卖家账号的实用方法

分享如何安全运营多个eBay卖家账号的实用方法

“我们在eBay上已经销售了20多年&#xff0c;有多个eBay账户。但我们的一个小账户最近收到了限制通知&#xff0c;所以我们提供了必要的文件。然而&#xff0c;我们震惊地发现&#xff0c;我们的账户被永久暂停。我们的另外两个账户也被限制销售。"一位eBay用户分享道。 在…
阅读更多...
AscendCL运行时资源异常问题案例

AscendCL运行时资源异常问题案例

AscendCL&#xff08;Ascend Computing Language&#xff09;是一套用于在昇腾平台上开发深度神经网络推理应用的C语言API库&#xff0c;该API库中提供运行资源管理、内存管理等基础API。 本期就分享几个关于运行资源管理、内存管理等基础API问题的典型案例&#xff0c;并给出…
阅读更多...
AutoSAR系列讲解（入门篇）4.2-BSW的I/O功能

AutoSAR系列讲解（入门篇）4.2-BSW的I/O功能

一、架构与术语解释 这里主要是说I/O的功能&#xff0c;而其中会用到一些模块&#xff0c;下面途中我将用到的模块都高亮显示了&#xff0c;并且放大到了右边的途中展示其中的子模块&#xff08;该子模块就是BSW中最小的单位了&#xff0c;如其中的ADC子模块&#xff09;。这里…
阅读更多...
基于 unity 配置 adb

基于 unity 配置 adb

1.打开环境变量配置path的环境 2 找到自己的unity安装目录,找到对应路径 配置到 path 属性中 C:\~\Editor\2021.3.0f1c1\Editor\Data\PlaybackEngines\AndroidPlayer\SDK\platform-tools 3 应用保存即可
阅读更多...
python numpy 多维数据广播

python numpy 多维数据广播

广播规则&#xff1a;从最右侧开始广播。 Broadcasting — NumPy v1.25 Manual 截图 下面给出一些样例&#xff1a; 三维矩阵广播 a np.array([[[0,0],[0,0]],[[0, 0],[0, 0]]])print(-*10, a, -*10) print(a.shape) print(a)b np.array([[[1]],[[2]]]) print(-*10, b, -*…
阅读更多...
Excel表格密码去除，轻松解锁大全

Excel表格密码去除，轻松解锁大全

【】在线Excel表格解密方法&#xff1a;找回Excel密码、去除密码、安全简单易操作 【】 对于使用Excel表格的用户来说&#xff0c;有时候会遇到表格被密码保护的情况&#xff0c;无法编辑或查看内容&#xff0c;这给工作和学习带来了一些困扰。但是&#xff0c;不用担心&#…
阅读更多...
使用vue+element开发一个谷歌浏览器插件

使用vue+element开发一个谷歌浏览器插件

谷歌浏览器插件-二维码生成器 使用vue2element ui开发&#xff0c;参考文章&#xff1a; https://blog.csdn.net/qq_35606400/article/details/123183420 代码地址&#xff1a;https://github.com/changwenxia/chrome-qr-tools 开发过程&#xff1a; 1.将package.json里的mai…
阅读更多...
人脸识别损失函数总结

人脸识别损失函数总结

1、Softmax Loss 公式 特点 Softmax鼓励不同类别的特征分开&#xff0c;但没有对特征分离的距离进行限制 2、L-Softmax Loss 公式 特点 增加margin角度参数m&#xff0c;压缩类内角度范围&#xff0c;实现类内紧凑&#xff0c;增加类间决策边界间隔参数m压缩了cos函数角度…
阅读更多...
最新文章

Copyright @ 2022~2023