定位：签到题，tag：博弈，思维

题意：n个石圈，两个人轮流对石子进行染色，相邻不能同色，不能操作的人输，问谁赢。

10pts

白送，测试点6主要作用是引导选手发现堆大小为1时后手必败。

40pts

暴力dfs或者状压dp都可以。实际上拿40分不需要打代码，在纸上左右互博一下，然后把答案打个表直接输出即可。

60pts

如果大胆猜想，每一堆的胜负状态其实不随两个人的决策而改变，就会发现输赢其实之和必败堆的奇偶数目有关，所以只要统计必败堆的个数，用必败堆的奇偶数目判断即可。

100pts

无论是通过暴力还是纸上自己推一下画画，都不难发现，当只有一圈石子的时候，除非大小为1，不然后手一定必胜。所以只需要统计1的个数即可，1的个数为奇数则先手必胜，否则后手必胜。

简单证明一下为什么这个博弈跟先手与后手的操作完全无关。

根据题意：不能有相邻同色的石子，考虑终态，终态一定不存在这种情况。

我们先考虑一个圈的情况，当一个圈无法被涂上任何颜色的时候。

我仅画出了几种情况。

可以推断，(其实也是必然啦)——颜色一定是交替出现的。

因为如果两个相同颜色连续，必定中间存在至少一个空位。

所以，当一个圈无法涂上任何颜色时，颜色出现的数量一定是偶数。所以后手一定会赢。

当且仅当，石圈的大小为1时，先手可以赢。

扩展到n个圈其实也是相同的，只不过每存在一个大小为1的石圈，都会导致胜负状态发生转换，所以只需要统计大小为1的石圈数目即可。

T2 乃爱与城市拥挤程度

定位：中等题，tag：树DP，换根法/树DP的up and down。

题意：给一颗树，问你每个节点作为根节点时，距离它小于k的节点数目，以及这些节点动态权值的乘积。

10pts

对于测试点10，因为是单链，所以可以O(1)直接算。

40pts

对于测试点1，2，3，枚举每个点，写个dfs跑一下按题意模拟统计一下即可。

70pts

对于测试点4,5，可以写一些对于测试点特化的dp，或者利用树结构随机进行一些dfs 上的优化。

80pts

单链其实也可以dfs…因为没分叉所以跑的很快，优秀点的暴力应该拿到80了吧。

100pts

一看就是树DP，然后也就没什么滑头搞就完了，然后这道题是无根树DP，属于树DP中稍麻烦一点的情况。

对于无根树的dp套路其实就两种，一种是换根法，另一种是树DP的up and down。

换根法：

先随便找一个点作为根节点使用，得到整个树每个节点的dp信息并且储存起来。

考虑相邻节点换根，也就是假设根节点为x，然后整颗树的dp信息是以x为根的基础上进行构建的，y节点为x节点的直接孩子。我们发现当整棵树的根节点由x转换为y时，改变的dp信息其实非常少，往往只影响到x,y两个节点。

如果你DP方程是那种加加减减，乘乘除除的话就更适合使用换根法了。

因为它们有对应的“逆操作”。将DP方程反着转移就可以抵消这种转移带来的影响，因为我们可以写一个link一个cut，对应转移和逆转移。利用link cut，我们可以像平衡树一样把所有的点都拎上来当根。

如果方程没有对应的逆操作，比如 max,min，就比较麻烦了，一般解决方法是借助数据结构(一般常用的方法是开n个multiset/multimap或者手写平衡树)，或者维护前k大/小值来做到，这个时候推荐使用下面的方法。

up and down：

先做一个自下而上的up dp，再做一个自上而下的子树down dp，然后在每个节点处合并两个dp数组的信息，得到以每个点作为根节点的dp信息。

x表示当前节点，y节点是x节点的父节点，那么以x作为根节点的dp信息为x的down dp合并其父节点y的up dp。

上述这两种方法换根法的常数比较大（大概慢2~3倍），好处是可以很方便的枚举所有根，有时题目要求导致不得不使用这种方法，建议都掌握，平时用up and down的技巧。

T3小w的魔术扑克

定位：中等偏难题，tag：图论模型，并查集，树状数组，离线算法

题意：k张正反面的卡片，打出时只能选择一面，查询q次，每次问是否能组成l到r的顺子。

10pts

对于测试点4，搞个前缀和判一下就行了。

40pts

写个暴力dfs，或者状压DP随你搞…反正数据范围很小。甚至暴力网络流都可以40分

100pts

如果能想到图论模型，这个题就解了一半了。对于每个面值，由于在一个查询中它最多需要一次。所以我们可以把每个面值都当成是一个节点，对于一张牌，我们都建一条连接它正反两面两个面值的边。建好模型以后，我们不难发现，如果对于一个大小为N的连通块有至少N条边，那么这个连通块一定能满足保证每个面值都能够被提供至少一次。只有一种连通块特殊，也就是当连通块的大小为N，并且它具有N-1条边时，无论怎么调整，都会漏掉一个面值无法打出，大小为N，具有N-1条边的连通块，那也就是树。

所以我们先找树，dfs并查集啥玩意都ok，总之找出所有的树就可以了。

然后我们想这个问题的反面：什么样的顺子是不能满足的，我们发现，如果你的顺子完全包含了一颗树，那这个顺子就由于上述的原因无法构造。问题来了？如何判断一个顺子是否完全包含树？

先求出每一颗树上节点编号的最小值与最大值，构造一个约束线段，约束线段的左端点为树上节点编号的最小值，右端点为树上节点编号的最大值。

接下来问题转化成了线段覆盖问题：

即：给定查询线段l,r，问你查询线段是否至少完整的覆盖了任意一个约束线段。如果存在则输出No，反之输出Yes。

这个就是个经典问题了，按照线段的右端点排序然后离线树状数组。对于每一个约束线段都将它的左端点赋成1，然后查询，查询区间和是否为0即可。