首页 > 其他分享 >点分治

点分治

时间：2024-09-04 21:37:10浏览次数：6  
标签：arr int 分治 ++ fa maxn root

先写静态点分治，带修改的还没学，咕咕咕

点分治是用于处理树上简单路径统计的一种算法，利用分治的思想，对每一课子树统计答案，最后累加（看起来就很暴力）

所以我们要对其进行优化，将每一棵树按重心进行分割，再逐个处理子树，整体复杂度在 \(O(nlog_n)\) 左右

求重心

需要 \(dfs\) 一遍，对每一个节点开一个变量记录子树中最大的子树的 \(size\) ，让最大的 \(size\) 最小即可

点击查看代码 
void get(int x,int fa)
{
	size[x]=1,wt[x]=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		get(y,x);
		size[x]+=size[y],wt[x]=max(wt[x],size[y]);
	}
	wt[x]=max(wt[x],siz-size[x]);
	if(wt[root]>wt[x])root=x;
}

分治过程

分治的方法大概有两种，一是求整棵树对答案的贡献，再把子树中不合法的去了，类似容斥，二是一个一个子树合并来统计答案

相比而言代码量差不多，但第二个更泛用一些。

板子什么的我就随便一放，毕竟题和题的代码不是完全一样的。。。

方法一，摘自《聪聪可可》 
void lsx(int x,int d,int fa)
{
	arr[++cnt]=d;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		lsx(y,d+val[i],x);
	}
}

int calc(int x,int d){
    cnt=0; lsx(x,d,0); int l=1,r=cnt,sum=0;
    sort(arr+1,arr+cnt+1);
    for(;;++l){
        while(r&&arr[l]+arr[r]>k) --r;
        if(r<l) break;
        sum+=r-l+1;
    }
    return sum;
}

void solve(int x){
    ans+=calc(x,0); vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
    	int y=to[i];
    	if(vis[y])continue;
    	ans-=calc(y,val[i]);
        root=0, siz=size[y],get(y,0);
        solve(root);
	}
}
方法二，摘自《Race》 
void lsx(int x,int d,int fa,int deep)
{
	if(d>k)return ;
	arr[++cnt]=d;
	c[d]=min(c[d],deep);
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		lsx(y,d+val[i],x,deep+1);
	}
}

void solve(int x,int fa)
{
	vis[x]=1;
	b[0]=0,q[0]++,a[++sum]=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(vis[y]||y==fa)continue;
		lsx(y,val[i],x,1);
		for(int j=1;j<=cnt;j++)
		{
			if(q[k-arr[j]]) ans=min(ans,(long long)c[arr[j]]+b[k-arr[j]]);
		}
		for(int j=1;j<=cnt;j++)
		{
			b[arr[j]]=min(b[arr[j]],c[arr[j]]);
			c[arr[j]]=0x7f7f7f;
		}
		for(int j=1;j<=cnt;j++) q[arr[j]]++,a[++sum]=arr[j];
		cnt=0;
	}
	for(int i=1;i<=sum;i++) b[a[i]]=0x7f7f7f,q[a[i]]--;
	sum=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(vis[y]||y==fa)continue;
		root=0,siz=size[y],get(y,0);
		solve(root,0);
	}	
}

题目

鉴于洛谷被封ip了，就不放链接了。。。

  • 1：《聪聪可可》

开桶记录一下模3后为0,1,2，的边的个数，直接算即可

点击查看代码 
#include<bits/stdc++.h>
const int maxn=1e5+10; 
using namespace std;
int n,k,ans,root,size[maxn],siz,wt[maxn],arr[maxn],cnt;
int head[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],tot;
int f[3];
bool vis[maxn];

void add(int x,int y,int z)
{
	to[++tot]=y;
	val[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
void addm(int x,int y,int z)
{
	add(x,y,z);add(y,x,z);
}

void get(int x,int fa)
{
	size[x]=1,wt[x]=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		get(y,x);
		size[x]+=size[y],wt[x]=max(wt[x],size[y]);
	}
	wt[x]=max(wt[x],siz-size[x]);
	if(wt[root]>wt[x])root=x;
}

void lsx(int x,int d,int fa)
{
	f[d%3]++;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		lsx(y,d+val[i],x);
	}
}

int calc(int x,int d)
{
	memset(f,0,sizeof f);
	lsx(x,d,0);
	return f[0]*(f[0]-1)/2+f[1]*f[2]; 
}

void solve(int x)
{
	ans+=calc(x,0);vis[x]=1;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(vis[y])continue;
		ans-=calc(y,val[i]);
		root=0,siz=size[y],get(y,0);
		solve(root);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		addm(x,y,z);
	}
	wt[root=0]=0x7f7f7f;
	siz=n;
	get(1,0);
	solve(root);
	int a=ans*2+n,b=n*n,p=__gcd(a,b);
	cout<<a/p<<"/"<<b/p<<'\n';

	return 0;
}
  • 2: 《Race》

记录一个每个边权是否出现，所用的最小边数，这里方法一不太适用，所用只能按子树合并，直接把已合并的子树和要合并

的子树的贡献统计即可，记得清空

点击查看代码 
#include<bits/stdc++.h>
const int maxn=2e5+10; 
using namespace std;
int n,k,root,size[maxn],siz,wt[maxn],arr[maxn],cnt,b[1000005],c[1000005];
int head[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],tot,sum,a[1000005],q[1000005];
long long ans;
bool vis[maxn];

void add(int x,int y,int z)
{
	to[++tot]=y;
	val[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
void addm(int x,int y,int z)
{
	add(x,y,z);add(y,x,z);
}

void get(int x,int fa)
{
	size[x]=1,wt[x]=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		get(y,x);
		size[x]+=size[y],wt[x]=max(wt[x],size[y]);
	}
	wt[x]=max(wt[x],siz-size[x]);
	if(wt[root]>wt[x])root=x;
}

void lsx(int x,int d,int fa,int deep)
{
	if(d>k)return ;
	arr[++cnt]=d;
	c[d]=min(c[d],deep);
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		lsx(y,d+val[i],x,deep+1);
	}
}

void solve(int x,int fa)
{
	vis[x]=1;
	b[0]=0,q[0]++,a[++sum]=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(vis[y]||y==fa)continue;
		lsx(y,val[i],x,1);
		for(int j=1;j<=cnt;j++)
		{
//			cout<<arr[j]<<"! "<<q[k-arr[j]]<<endl;
			if(q[k-arr[j]])
			{
//				cout<<ans<<"!";
				ans=min(ans,(long long)c[arr[j]]+b[k-arr[j]]);
			}
		}
		for(int j=1;j<=cnt;j++)
		{
//			cout<<arr[j]<<"!"<<endl;
			b[arr[j]]=min(b[arr[j]],c[arr[j]]);
			c[arr[j]]=0x7f7f7f;
		}
		for(int j=1;j<=cnt;j++)q[arr[j]]++,a[++sum]=arr[j];
		cnt=0;
	}
	for(int i=1;i<=sum;i++) b[a[i]]=0x7f7f7f,q[a[i]]--;
	sum=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(vis[y]||y==fa)continue;
		root=0,siz=size[y],get(y,0);
//		cout<<root<<"!"<<'\n';
		solve(root,0);
	}	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		x++,y++;
		addm(x,y,z);
		if(z==k)
		{
			cout<<1<<'\n';
			return 0;
		}
	}
	wt[root=0]=0x7f7f7f;
	memset(b,0x7f,sizeof b);
	memset(c,0x7f,sizeof c);
	siz=n;
	ans=1e17;
	get(1,0);
//	cout<<root<<"!"<<'\n'; 
	solve(root,0);
	cout<<(ans>=n?-1:ans)<<'\n';

	return 0;
}
/*
4 3
0 1 1
1 2 2
2 3 4
*/
  • 3:《tree》

对答案贡献的只有过根的路径，把到子树根的距离都统计，双指针统计即可

点击查看代码 
#include<bits/stdc++.h>
const int maxn=4e4+10;
using namespace std;
int n,k,ans,root,size[maxn],siz,wt[maxn],arr[10001],cnt;
int head[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],tot;
bool vis[maxn];

void add(int x,int y,int z)
{
	to[++tot]=y;
	val[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}

void get(int x,int fa)
{
	size[x]=1;wt[x]=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		get(y,x);
		size[x]+=size[y],wt[x]=max(wt[x],size[y]);
	}
	wt[x]=max(wt[x],siz-size[x]);
	if(wt[root>wt[x]])root=x;
}

void dfs(int x,int d,int fa)
{
	arr[++cnt]=d;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa||vis[y])continue;
		dfs(y,d+val[i],x);
	}
}

int calc(int x,int d){
    cnt=0; dfs(x,d,0); int l=1,r=cnt,sum=0;
    sort(arr+1,arr+cnt+1);
    for(;;++l){
        while(r&&arr[l]+arr[r]>k) --r;
        if(r<l) break;
        sum+=r-l+1;
    }
    return sum;
}

void solve(int x){
    ans+=calc(x,0); vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
    	int y=to[i];
    	if(vis[y])continue;
    	ans-=calc(y,val[i]);
        root=0, siz=size[y],get(y,0);
        solve(root);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);add(y,x,z);
	}
	cin>>k;
	wt[root=0]=0x7f7f7f;
	siz=n;
	get(1,0);
	solve(root);
	cout<<ans-n;
	return 0;
}

/*
7
1 6 13 
6 3 9 
3 5 7 
4 1 3 
2 4 20 
4 7 2 
10
*/

标签：arr,int,分治,++,fa,maxn,root
From： https://www.cnblogs.com/oceansofstars/p/18397378

相关文章

  • 点分治与 cdq 分治
    声明：本文仅供阅读参考，请严格按照学校相关规定下使用希沃一体机。阅读本文，你需要知道一下几点：什么是希沃管家希沃管家，就是一个集成了学校管理、防护功能和系统保护于一体的东西。在希沃管家页面右上角，你可以看到你的学校名称，这就代表此设备已经接入学校的管理系统。在管理系统......
  • 线段树分治
    前置知识：可撤销化并查集注意：可撤销化并查集的作用和删边不一样，其只能撤销最近的一次操作。既然只需撤销，那么只需在合并并查集时用个vector记录下合并的哪两个点，撤销时就直接还原就行了。这里要强调一下，可撤销化并查集不能路径压缩，只能启发式合并。代码intf[MAXN],sz[MAXN......
  • 算法设计与分析：实验二 分治法——最近点对问题
    实验内容：对于平面上给定的N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。要求随机生成N个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离。分别对N=100000—10......
  • 感染 点分治优化建图
    I国有\(n\)个城市，有\(n-1\)条道路连接，并且所有的城市相互可达。城市因为自身的交通因素，人口因素，有一个传染力\(r_i\)，一旦这个城市爆发疫情，会迅速感染其他距离小于等于\(r_i\)的其他城市，并且造成连锁反应。问一开始最少几个受到境外输入，会导致整个国家\(n\)个城市全部......
  • 【题解】Solution Set - NOIP2024集训Day14 CDQ分治
    【题解】SolutionSet-NOIP2024集训Day14CDQ分治https://www.becoder.com.cn/contest/5482「CF364E」EmptyRectangles*3000摆烂了。「SDOI2011」拦截导弹CDQ的例题，之前做过（现在试图自己再做出来。第二问只用在第一问里面记录每一次是从哪个\(j\)​转移过来的，以及......
  • Scratch编程深度探索：解锁递归与分治算法的奥秘
    标题：Scratch编程深度探索：解锁递归与分治算法的奥秘在编程的世界里，递归和分治算法以其精妙的逻辑结构和解决问题的能力而著称。Scratch，这款专为儿童和初学者设计的图形化编程工具，是否能够支持实现这样复杂的逻辑呢？本文将深入探讨Scratch在实现递归和分治算法方面的能力，并提......
  • （算法）计算右侧⼩于当前元素的个数————＜分治-归并排序＞
    1.题⽬链接：315.计算右侧⼩于当前元素的个数2.题⽬描述：3.解法（归并排序）：算法思路：这⼀道题的解法与求数组中的逆序对的解法是类似的，但是这⼀道题要求的不是求总的个数，⽽是要返回⼀个数组，记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩。但是在我们归并排序的过程中，元素的下......
  • （算法）翻转对————＜分治-归并排序＞
    1.题⽬链接：493.翻转对2.题⽬描述：题⽬解析：翻转对和逆序对的定义⼤同⼩异，逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要⼤于后⾯某个数的两倍。因此，我们依旧可以⽤归并排序的思想来解决这个问题。3.解法（归并排序）：算法思路：⼤思路与求逆序对的思路⼀样，就......
  • Codeforces Round 967 (Div. 2) C题 类分治解法
    废话不多说,先上代码t=int(input())whilet>0:n=int(input())pre_d={1:[iforiinrange(2,n+1)]}pair_l=[]whilelen(pre_d)!=0:item=pre_d.items()now_d={}fork,vinitem:forii......
  • 点分治
    点分治点分治是一个求树上路径问题的算法，算法流程通常是：找到子树中的重心，计算重心的子树的每一个点与重心的路径的数据，接着统计整体答案。CloseVertices思路很明显，这是一道点分治题目，但有两个限制条件，考虑将两个条件排序起来，双指针找第一个条件，树状数组维护第二个条件，但是同......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99