点分治

本文主要是介绍点分治，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

点分治常用于树上路径统计等问题。

点分治

每次分治过程大致如下：

• 我们先求出当前连通块树的重心；

• 处理与重心有关的答案；

• 删除重心

• 递归处理与重心相连的子连通块。

伪代码如下：

void solve(int x)
{
	 Find1(x,0),Find2(x,0); // 找到重心 rt 
	 // 处理和 rt 有关的答案
	 used[rt]=true;
	 for(/*与 rt 直接相连并且没有被删除的节点*/) solve(ver);
}

P3806 【模板】点分治

P4178 Tree

树上 \(0/1\) 背包：给定一棵树，每个点上有一个物品有一个价值 \(w_i\)，\(m\) 次询问，每次询问 \(u\) 到 \(v\) 的路径上选择 \(k\) 个物品的最大价值。

P6326 Shopping

动态点分治

咕咕咕

这篇关于点分治的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！