【拾题杂谈】LuoguP2607 [ZJOI2008] 骑士
题面：[ZJOI2008] 骑士题目描述Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照 $1$ 至 $n$ 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
输入格式第一行包含一个整数 $n$，描述骑士团的人数。
接下来 ...
【算法介绍】基环树
算法简介：稳固阵线的魄力实话实说，这个被叫做基环树东西，没有什么强制的算法。本质上来讲，这是一种特殊的图，因为他特殊的性质，存在一种方式去统计和综合上面的信息，所以被单独拿出来讲了。
基环树，这个名字可以仍未是基于环的树，这个思维去解决问题的思路，还有答案的计算已经图的构建，都和环离不开关系，所谓基环基环，就是有环且仅有一个环的树。有时候也被称为章鱼图
算法基础：诱导殉爆的狙击那么首先，我们来介绍基环树的基本相关内容，首先给出一个基环树的图片。
说实话，这张图片可能画的不够明显。我们会发现这个被称为基环树的结构分为两个部分：
中间的环。树周围的分支，都围绕着中间的那四个环节点连出来。
周围的支。环的每一个节点，都可以看做一个以当前环节点为根的子树。
这和基环树的定义有关，一棵树增加一条边使得原图存在了一个环，这就是基环树。
而基环树处理问题的思路，就是分别处理每一个子树，然后再通过环统计一些答案。这就是基环树处理问题的基本思想，下面给出一个实例尝试一下。
算法演示：娴熟复装的技巧那么我们现在就给出演示实例。比如说我们要求基环树的直径，或者说距离最远的两个点对。这里给出一道例题：I ...
【基础语法】第一篇之 “读入输出”
基础语法之“读入输出”
基本介绍在 C++ 读入有两种流派，第一种是 C++ 新出品的 cin/cout 代表的 IOS 流派。第二种是传承自 C 语言的 scanf/printf 代表的旧语法流派。当然还有一些人会使用 快读/快写 等高速读入方式，后面的文章会提及。
IOS 流派
读入
一般来讲，在新手入门时，推荐使用$cin$来读入，其格式类似于：
123456789#include<bits/stdsc++.h>#include<iostream>// iostream 是包含 cin/cout 的头文件，当然包括在万能头里，所以如果引用了万能头，就不必担心用不了 cin/cout 了using namespace std;// 另外，cin/cout 还依赖于 C++ 新出的 std 库，也就是说我们必须引用 std 命名空间才可以，就是上面那一句话，不然的话我们要在所有和 std 有关的工具前面加上 std:: 这是命名空间的引用方式，以后的文章也会提及，举个例子，如果没有引用 std 库，那么 cin/cout 会变成 std::cin/std: ...
【算法介绍】扫描线思想
算法简介：号 · 仙蕊玲珑这篇文章就是继二维数点里挖下的坑的扫描线内容了。对于扫描线问题，其实是非常广泛的，就像动态规划一样。他主要是提供了一个在二维平面上用平行于坐标轴的线一个一个扫描过来的思想。总归一句话：只有你想不到，没有你扫不到。
友情链接：
【算法介绍】二维数点 | 祝馀宫
只要你可以按照题目的意思建立出可以通过题目的坐标系和线段，使其可以用扫描线扫出来，那么它就是可以的！
算法思想：武 · 西风长枪首先，既然叫做扫描线，那么上面叫做扫描呢？顾名思义，扫描扫描，从下到上扫一遍就可以了，但是扫描线其实还有一个特点，扫描线。其实所谓扫描线思想，就是把问题转化成一些线段，去按照某个顺序扫描他，然后顺便处理出问题。
我们可以先给出一个扫描线的经典问题，求矩形面积并。所谓矩形面积并，就是一堆矩形叠在一起，重复覆盖的地方只算一次，当然只出现一次的也是算一次（
那么这题首先第一眼应该都是暴力，毕竟大家都没什么好的思路去做这样奇怪的题目，那么，如果是扫描线呢？他其实是可以做出这样的题目的。为什么，我们来想想矩形是什么。小学大家就学过老师的名言：点动成线，线动成面。其实矩形的本质，就是一个 ...
【算法介绍】二维数点
算法简介：一箭双丘丘！其实吧，二维数点单独来讲不能算是一个算法，它泛指一种在二维平面上数有多少个点或类似的问题。涉及的数据结构比较广，也算是比较杂的一篇文章了。
二维数点大概有两种：静态的和动态的。根据题目给出的动静之分，我们可以大致知道用什么数据结构，一般来讲，单点动态的我们偏向用树状数组等操作，多点动态应该除了线段树没谁了；还有就是静态，一般来讲非必要情况都是树状数组，毕竟码量低，然后有时候会有扫描线的题目。扫描线还没讲，先挖个坑罢（
这里就挑几个二维数点的实例看看，大概意会一下。
算法演示：一触即发例题一：烧起来啦！大秦为你打开题目传送门
题面翻译平面上有n个点，还有一个长度为⑨的数列$a_1,a_2……a_9$满足$\sum_{i=1}^na_i=n $
你需要画两条水平直线和两条竖直直线将平面划为⑨各部分，每部分点数记为$b_1,b_2……b_9$
要求b是a的一种排列
你的直线坐标可以是实数，构造一组解，或无解（输出-1）
题目思路虽然说他是紫题，但是太简单了，不必有任何压力（我是一眼秒的
让你把一堆点分成一个九宫格（其实是找九宫格中间的四条分界线）然后每一个格子一定是给 ...
【拾题杂谈】LuoguP2486 [SDOI2011] 染色
题面：[SDOI2011] 染色题目描述给定一棵 $n$ 个节点的无根树，共有 $m$ 个操作，操作分为两种：
将节点 $a$ 到节点 $b$ 的路径上的所有点（包括 $a$ 和 $b$）都染成颜色 $c$。
询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。
颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。
输入格式输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 $n$ 和操作个数 $m$。
第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数 $w_i$ 代表结点 $i$ 的初始颜色。
第 $3$ 到第 $(n + 1)$ 行，每行两个用空格隔开的整数 $u, v$，代表树上存在一条连结节点 $u$ 和节点 $v$ 的边。
第 $(n + 2)$ 到第 $(n + m + 1)$ 行，每行描述一个操作，其格式为：
每行首先有一个字符 $op$，代表本次操作的类型。
若 $op$ 为 C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 $a, b, c$，代表将 $a$ 到 $b$ 的路径上 ...
【拾题杂谈】LuoguP2590 [ZJOI2008] 树的统计
题面：[ZJOI2008] 树的统计大秦为你打开题目传送门
题目描述一棵树上有 $n$ 个节点，编号分别为 $1$ 到 $n$，每个节点都有一个权值 $w$。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点 $u$ 的权值改为 $t$。
II. QMAX u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值。
III. QSUM u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和。
注意：从点 $u$ 到点 $v$ 的路径上的节点包括 $u$ 和 $v$ 本身。
输入格式输入文件的第一行为一个整数 $n$，表示节点的个数。
接下来 $n-1$ 行，每行 $2$ 个整数 $a$ 和 $b$，表示节点 $a$ 和节点 $b$ 之间有一条边相连。
接下来一行 $n$ 个整数，第 $i$ 个整数 $w_i$ 表示节点 $i$ 的权值。
接下来 $1$ 行，为一个整数 $q$，表示操作的总数。
接下来 $q$ 行，每行一个操作，以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式给出。
输出格式对 ...
【拾题杂谈】LuoguP3384 【模板】重链剖分/树链剖分
题面：【模板】重链剖分/树链剖分大秦为你打开题目传送门
题目描述如题，已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。
2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。
4 x 表示求以 $x$ 为根节点的子树内所有节点值之和
输入格式第一行包含 $4$ 个正整数 $N,M,R,P$，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。
接下来一行包含 $N$ 个非负整数，分别依次表示各个节点上初始的数值。
接下来 $N-1$ 行每行包含两个整数 $x,y$，表示点 $x$ 和点 $y$ 之间连有一条边（保证无环且连通）。
接下来 $M$ 行每行包含若干个正整数，每行表示一个操作。
输出格式输出包含若干行，分别依次表示每个操作 $2$ 或操作 $4$ 所得的结果（对 $P$ 取模）。
样例 #1样例输入 #11 ...
【算法介绍】树链剖分
算法简介：空取奇思的手艺接下来的内容是关于链剖分的，没错，就是链剖分，那个每次去和线段树凑在一起用的算法，其实线段树早就已经讲过很久了，这个链剖分着实讲的有点晚，不过无伤大雅，这次讲清楚便是。
友情链接：
【算法介绍】普通线段树 | 祝馀宫【算法介绍】线段树合并 | 祝馀宫
链剖分大概分为三个主流的：
树链剖分（也叫重链剖分）
实链剖分（就是熟知的恶魔 LCT ）
长链剖分（和重链剖分齐名的一种剖分方式）
这一篇的内容就是关于重链剖分的，后续可能会接着把几个连剖都搞完。
算法演示：巧言贴耳的诱引算法推导：玄迷灵敏的指法首先，重链剖分其实是非常形象的。他的名字：重链剖分的重，直接表明了他的主要思路，通过轻重儿子剖分。所谓轻重儿子，我们把一个节点 $u$ 的儿子中，子树（包含那个儿子）的大小中最大的，就是重儿子，记作 son[u] ，S也就是 $u$ 的重儿子。（ sz[u] 表示以 $u$ 为根的子树大小）
sz[son[u]] = \max_{v\ \in\ \operatorname{child}(u)} sz[v]那么什么叫做以轻重儿子剖分呢？我们在定义下面的内容，父亲连 ...
【奇技淫巧】特殊思维题的复杂度分析
算法简介：堆叠真空域在做题的过程中，我们经常会发现那些看上去是纯暴力，但是复杂度却是 $n\log n$ 或者其他的算法或思想。这些题抓住了做题人在计算复杂度时候的失误，从而达到了思维难度提升的效果。他们通常题目评级不高，但是却总是很难想到。
算法演示：不羁型贝特大致思想：零失误少女这类题目有一大特点：倍增
比如说这些题目 P9974【USACO23DEC】Candy Cane Feast B 、【ABC315F】Shortcuts 等等等等，他们的题目或多或少都点到了一个关键字二的幂次、翻倍。比如说 USACO 的这道，虽然没有直接提到翻倍，但是我们会注意到奶牛最多吃到和自己一样高的糖果，也就是说第一只奶牛会一直翻倍，这也保证了复杂度。
这样倍增的性质，通常是隐蔽的，有些甚至感觉微小的不可发现，这也是成就了这些题目难度的主要因素。而这种倍增是丰富多样的，比如说刚刚给出的第二题，跳过的代价显而易见是极高的，我们发现最大距离会远小于跳过多个点，更具这个性质，我们可以把题目的空间以及时间复杂度压到 $\log n$ 。这是一种倍增代价，去发现优劣的思路。
除此之外，比如说启发式合并，每次合 ...
