开拓计划4-二叉树与并查集二叉树二叉树的概念Q：什么是树？A：一种有\(n\)个节点最多有\(n-1\)条边的图。Q：什么是二叉树？A：每个节点都最多只有两个子节点的树。二叉树和递归Q：二叉树和递归有什么关系？A：在执行递归的时候总是会自己调用自己，每一次调用都会产生新的一层，新

NKOJ3924parity思路：带权并查集实现方法并查集每个点的点权表示其奇偶性，奇偶性有很多种表示方法。一种是在计算新的值的时候直接加起来\(\bmod2\)，另一种用了\(\operatorname{xor}\)的性质，当\(0\operatorname{xor}1\)\(x\)次时，\[0\operatorname{xor}1=\begin{cas

NKOJ1209并查集【NOI2001Day1T3】食物链思路：带权/种类并查集方法一实现方法用带权并查集带的权值是边权，不是点权，用来表示两点间的关系，但为了方便记录还是用点权，每个点记录到根节点的权值。在getf函数中注意更新是到根节点之间的权值，用\(val_x=(val_x+val_{fa_x})\bm

NKOJ2107【并查集】可爱的猴子思路：普通并查集+图的遍历更新答案实现方法首先使用时光倒流思想解决删边的问题。注意提前把没有删过的边提前建上。接着用一个图记录猴子之间的拉手关系，每次要更新答案时都遍历与当前节点连着的节点将其答案更新，只有在\(1\)号节点与当前节

NKOJ1206【NOI2002Day1T1】银河英雄传说思路：和NKOJ2281一样实现方法移动操作完全一样。计算操作的区别在于，一个是直接输出到根节点的距离，另一个实际上是前缀和思想，用\(x\)到根的距离减去\(y-1\)到根的距离，就是\(x\simy\)之间的距离。代码#include<cstdio>#in

NKOJ1407地毯填补问题思路分治算法经典题。实现方法把公主看成障碍物，填的地毯也是障碍物。观察题目发现迷宫大小为\(2^k\times2^k\)格，每次正好可以四等分。每次填充的地毯正好填三格，正好留下一格障碍物。代码#include<bits/stdc++.h>#defineintlonglongusi

NKOJ3631密码锁思路BFS经典题。实现方法用一个结构体存储当前密码锁的状态和已经走过的步数。将开始的状态入队。每次取出队首，枚举所有可能情况。每一位的上下拨动。每两位之间的交换。共\(11\)种情况。给入队的情况打标记。代码#include<map>#include<qu

NKOJ2110美丽的星空思路洪水填充(BFS)+多边形全等的判定。实现方法这道题比较复杂，分为三个步骤。用BFS求出有哪些星座并编号。两两判全等。多边形的全等判定定理：如果两多边形每两个点之间的距离和相等，则它们全等。如果两个多边形全等，就将新的打上旧的的标记。

二分练习plus-二分二分的理论基础二分的作用Q：二分有什么作用？A：二分可以在\(O_{\logn}\)的时间内找到特定的值。二分的原理Q：二分的原理是什么？A：二分的本质是分治，把从一个大区间里找东西的问题根据找的东西的大小分成两半，只查找答案可能在的范围，不可能在的范围不管