点分治

点分治，也叫重心剖分，是一种用于树形数据结构的分治思想的算法，解决树上满足条件的路径统计问题。点分治的核心思想是通过选择树的重心结点，将树划分为若干子树，然后递归地在这些子树上应用相同的策略，从而有效地解决问题。

实现步骤

1. 确定当前树的中心，设为根结点，开始点分治算法；
2. 枚举下一个结点，通过 dfs 更新子树贡献；
3. 清空当前使用的统计答案的数据结构，比如数组或树状数组（不建议完全清零，可能复杂度退化），删除当前结点；
4. 递归处理各个子树，回到步骤 $1$。

因为每一次选的是重心，所以每一个划分的子树大小不超过 $\frac{n}{2}$，所以递归的深度为 $O(\log n)$，每一层递归中需要 $O(n)$ 的时间复杂度来处理当前树。即跑点分治实现的时间复杂度为 $O(n \log n)$（不包含实现的数据结构的时间复杂度）。

平衡树

全称是二叉搜索平衡树

二叉搜索树：对于一棵二叉树，每个节点有权值 $val$，任意节点 $x$ 的左子树的权值小于等于 $val_x$，右子树反之。

二叉搜索树的优点：

1. 具有单调性，可以 $log_2$ 的时间查找。
2. 二叉搜索树的中序遍历是单调不减的，可以将下标当做权值，这样一个序列可以映射到一棵二叉搜索树。

为什么需要平衡树？

• 一个序列对应的二叉搜索树不唯一。我们希望找到高度最小的那颗应用。

若一棵二叉树的任意一个结点 $x$，其左右子树高度差不超过 $1$，称为二叉平衡树。

树链剖分

是一种将一棵树划分为若干条链的思想，划分后每个树上结点恰好在一条链中。

而一条链又可以转化为一段连续的区间，从而将树上问题转换为序列问题。

换根DP（二次扫描DP）

介绍

对于树形DP,若给定无根树，而问题的最优解与根节点相关，那么考虑换根DP。

通常可以将枚举根节点跑DP的时间复杂度由 $O(N^2)$ 降为 $O(N)$。

赛前训练2-连通性系列问题——总结

A

洛谷P2656

错误原因

double 的精度不够，应开 long double。

正解

1. 条边只有在环上时，才可能多次经过，且一定会经过足够次直到边权为 $0$；
2. 输入时维护 x[i],y[i],w[i],kw[i] 其中 kw[i] 表示第i涤边迭代经过的总边权和；
3. 缩点建新DAG图，跑最长路。

1931年9月18日

震惊中外的九一八事变爆发

白山黑水间，中国人民奋起反抗

揭开抗战14年的序幕

也成为世界反法西斯战争的起点

阅读全文 »

最小割问题

对于给定的网络流模型，其最小割是指删除边权和最小的边集，使得 $s$ 到 $t$ 不连通。

最小割等于最大流，因为增广路的流量限制是由这些权值的边，方案不一定唯一。

状压DP（二）

洛谷P3092

P3092 [USACO13NOV] No Change G

这道题，我们一般定义 $dp_{i,j}$ 为硬币使用了二进制下的 $i$，付到第 $j$ 个人的最多剩下多少钱。

不过 $2^{16}\times 10^5=6,553,600,000$，会超过空间限制。

我们发现“最多剩下多少钱”没有用，因为可以通过使用情况算出。

定义新的状态 $dp_{i}$ 表示硬币使用了二进制下的 $i$ 的最多能付到的人，可以通过前缀和加二分优化计算。

状压DP

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

——OI-WIKI

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.