主要思路
这个题还是比较简单的。
发现在生成树上放一个 \(2\) 之后，剩下与该点距离为偶数的点都已经确定了。所以对于一个连通块而言，被染成 \(2\) 的方式只有两种。
那么我们可以对这些连通块做一个背包，然后来判断是否有 \(n_2\) 的染色方案。
剩下的点随便染色即可。
Continue reading →POJ1639:Picnic Planning 题解
大体思路
做过 LCT 么？（做过基本上就可以切这一道题）
考虑把跟节点先去掉，然后会产生很多个联通块：每一个连通块求出最小生成树，然后找到整个连通块与根节点连接的最小边，连上。
之后如果还剩下一定的可以使用的度数，我们可以考虑用根节点剩余的边去更新整个最小生成树。具体而言，我们找到了一个\((1, v)\)未使用的边，然后我们找\(1 \to v\)上所有的边，找到一个差值最大的。如果这个差值是正数，那么加入这条边，删去之前的边，就会发现答案减掉了这个正差值。不停重复就可以得到答案。
LCT 的一类题目
LCT 简述
LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是，LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边，所以很多题目就可以打破一些限制进行求解。
「Fortuna OJ」Aug 10th – Group A 解题报告
A – 数学题
这道题二次函数的暴力分有 60 分，正解来自于论文。
这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：
结论 对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。
这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：
P3317:「SDOI2014」重建题解
矩阵树定理的运用
正常来讲，在矩阵树中，我们其实要算的东西就是这个：
\[ \sum_T \prod_{e \in T} p_e, \forall p_e = 1 \]
我们算的其实就是概率都为\(0/1\)的情况。现在我们要算：
\[ \sum_T \prod_{e \in T} p_e \prod_{e \notin T} (1-p_e) \]
我们可以考虑写成和式内仅与矩阵有关的式子：
\[ \sum_T \prod_{e \in T} p_e \frac{ \prod_e (1 – p_e) }{\prod_{e \in T} (1-p_e) } \]
合并积和式：
\[ \prod_e p_e \sum_T \prod_{e \in T} \frac{p_e}{1 – p_e} \]
然后我们把矩阵的内容改成\( \frac{p_e}{1 – p_e} \)就行了。
P4899:「IOI2018」 werewolf 狼人题解
解法
这道题是 Kruskal 重构树的裸题。我们先来考虑从\(s\)出发的人形状态，我们要找到一个点点权小于\(L\)的点，就相当于在 Kruskal 重构树上倍增找到最后一个小于\(L\)的点。我们把符合人形规律的 Krukskal 树记为 Tl，其中构造它的方式就是把原来图上所有边的边权赋值为端点的最大值，然后按最小生成树的方式去构造重构树；符合狼形规律的 Kruskal 重构树被记为 Tu，其中构造它的方式就是将端点编号最小值赋为边权，然后按最大生成树的方式构造。之后，我们再到主席树中求交集即可，如果有交集那么查询结果为一个不为零的数，输出\(1\)即可；没有交集那么查询结果即为\(0\)，输出\(0\)。