首页 > 其他分享 >Note - 树分治(点分治、点分树)

Note - 树分治(点分治、点分树)

时间:2024-08-16 19:48:45浏览次数:9  
标签:pre 子树内 int maxp 分治 Note 点分树 now

陈年笔记,现在可能不会了。

点分治

Q1:基本思想是什么?

将路径分为经过 \(u\) 和不经过 \(u\) 的两类,在每次分治中计算经过 \(u\) 的路径数量。

Q2:如何统计?

  1. 一般:遍历 \(u\) 的每个子节点 \(v\),把 \(v\) 子树内的节点记录下来,得到答案并更新数组。
  2. 容斥:把 \(u\) 子树内的节点都记录下来排序,双指针得到的 \(u\) 子树内点对数量,减去每个子节点 \(v\) 子树内的点对数量,即为经过 \(u\) 的路径的答案。*

Q3:如何保证复杂度?

每次 \(O(n)\) 寻找重心,子树大小降为最大 \(\lfloor size/2 \rfloor\),大概 \(\log(n)\) 层。每层遍历大概 \(n\) 个节点,复杂度上限 \(O(n\log(n))\)。

Q4:用途是什么?

统计树上满足条件的路径(点对)个数(或点权和等),一般条件和距离相关。

void findrt(int u,int f){
	siz[u]=1;
	maxp[u]=0;
	for(int i=fir[u];i;i=nex[i]){
		int v=to[i];
		if(vis[v]||v==f) continue;
		findrt(v,u);
		siz[u]+=siz[v];
		maxp[u]=max(maxp[u],siz[v]);
	}
	maxp[u]=max(maxp[u],sum-siz[u]);
	if(maxp[u]<maxp[rt]) rt=u;
}
void dfz(int u){
	vis[u]=1;
	
	//计算!!!
	
	for(int i=fir[u];i;i=nex[i]){
		int v=to[i];
		if(vis[v]) continue;
		rt=0;
		sum=siz[v];
		findrt(v,u);
		dfz(rt);
	}
}

边分治

其实和点分治差不多。

点分树

Q1:基本思想是什么?

通过点分治的方法递归,每次的得到 \(v\) 子树内的重心与 \(u\) 相连,建出重构树。

Q2:特殊性质?

  1. 最多 \(log(n)\) 层。
  2. 重构树上的 LCA(x,y) 必定在原树 x 到 y 的路径上,有 \(dis_{x,y}=dis_{x,LCA(x,y)}+dis_{y,LCA(x,y)}\)。*

Q3:如何运用特殊性质?

点分树又被成为动态点分治。
点分树和点分治一样适用于统计满足条件的路径的点权和,但点分树可修改点权,更加灵活,保证了每次只需查询或修改 \(log(n)\) 层。

Q4:具体实现?

  1. 得到重构树,其实只需记录 \(fa_u\)。
  2. 一个显然的思路是在重构树中将 \(now\) 不断变为父亲节点,得到在 \(fa_{now}\) 子树内但不在 \(now\) 子树内的贡献。
  3. 想想如何更新。我们用 \(f_i\) 存 \(i\) 子树中 \(i\) 的数据,\(g_i\) 存 \(i\) 子树内 \(fa_i\) 的数据。

示例:P6329 【模板】点分树

void modify(int x,int k){
	int now=x;
	while(now){
		F.modify(now,getdis(now,x),k);
		if(Fa[now]) G.modify(now,getdis(Fa[now],x),k);
		now=Fa[now];
	}
}
int query(int x,int k){
	int now=x,pre=0,ret=0;
	while(now){
		int t=getdis(now,x);
		if(t>k){
			pre=now,now=Fa[now];
			continue;
		}
		ret+=F.ask(now,k-t);
		if(pre) ret-=G.ask(pre,k-t);
		pre=now,now=Fa[now]; 
	}
	return ret;
}

标签:pre,子树内,int,maxp,分治,Note,点分树,now
From: https://www.cnblogs.com/zengzi/p/18359675

相关文章

  • Note - 高斯消元法(证明略)
    线性代数高斯消元法求解线性方程组高斯消元法是求解线性方程组的经典算法,还可以用于行列式计算、求矩阵的逆。部分代码From「SDOI2006」线性方程组doublea[N][N];//a[i][j]表示第i个方程中第j个元的系数,a[i][n+1]为等号右侧的常数项voidGauss(){for(inti=1;i<......
  • EndNote21.4安装教程(最新版)
    下载链接:https://docs.qq.com/doc/DSVZXTVRvYXdEd21q软件介绍、EndNote文献管理软件是由科睿唯安公司开发的文献管理软件,可用于帮助研究人员管理和组织参考文献、引用和注释,从文献检索、组织科研活动、撰写论文,到发表文章和共享科研成果,助力机构用户加速科研流程。EndNote......
  • 禁止使用 @NotEmpty 注解
    先上结论:@NotEmpty是一个容易让人产生误解的注解,因为他不是一个原子注解;@NotEmpty注解作用于string的话,很鸡肋,没有@NotBlank更简单暴力,容易理解;避免出现空格的问题;空格也没有什么具体业务场景;@NotEmpty作用于list的话也是很鸡肋,不如:@NotNull+@Size灵活容易理解;**......
  • 8个快速提升工作效率的印象笔记(Evernote)使用技巧,你掌握了吗?
    印象笔记(Evernote)是一款强大的笔记软件,它可以帮助用户更好地组织和管理信息。为了提升使用印象笔记的效率,以下是几个实用的技巧:1.快速记录想法1.1快速创建笔记印象笔记的电脑和手机客户端都有快速创建笔记的功能。在主屏向下滑动,可以在通知栏中添加笔记。如果下滑后没有......
  • 根号分治莫队
    莫队参考文章:莫队细讲——从零开始学莫队莫队算法——从入门到黑题oiwiki--普通莫队莫队简介莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前,莫队算法已经Codeforces的高手圈里小范围流传,但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时,只分析......
  • 点分治
    点分治以树的重心为根,对子树内的问题分治求解,时间复杂度可以做到\(O(n\logn\timesF(n))\),其中\(F(n)\)是解决经过根的问题所需要的处理。P3806模版给一棵有边权的树,多次询问树上是否存在距离为\(k\)的点对。\(n\le10^4,m\le100,k\le10^7\)假设现在\(rt\)是根,则......
  • 点分治
    参考博客概述点分治适合处理大规模的树上路径信息问题。——摘自OIWiki时间复杂度\(O(n\logn)\)(每次\(calc\)时间复杂度为\(O(size_{root})\))。对于树上的所有路径及一个假定的根\(rt\),有两种路径:经过\(rt\)的;不经过\(rt\)的。第一种路径显然分两部分(可以......
  • cdq分治
    我觉得呢,cdq的本质就是在归并排序消掉一维的影响来处理多维偏序问题。既然本质跟二分有关,那很容易猜到cdq处理k维偏序的时间复杂度为\(O(Nlog^{k-1}N)\)三维偏序问题:形如:$求满足条件a_i<a_j,b_i<b_j,c_i<c_j且\(j!=i\)的j个数比较常考的就是三维偏序,一般做法就是sort消掉一......
  • CDQ分治
    P3810【模板】三维偏序(陌上花开)CDQ模板题,考虑先按\(a\)排序,减掉一位,然后再\(CDQ\)分治一维,用树状数组维护最后一维还有本题特殊,去重操作不要忘记点击查看代码#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#definell......
  • 提升效率的印象笔记(Evernote)使用指南
    印象笔记(Evernote)是一个功能强大、跨平台的笔记管理工具,它不仅能帮助你记录日常笔记,还可以用于整理工作计划、管理项目、存储灵感和信息等。为了最大化地提高你的生产力,以下将介绍一些高效使用印象笔记的技巧,帮助你充分发挥其潜力。一、入门基础:理解印象笔记的基本概念1.1笔......