A、黑色气球

• 签到题
• ？

B、小吨的点分治

• 假设我们已经对一棵树进行了点分治得到对应的点分树。如果我 们删去原树中的一条边，把得到的两个连通块中的点分别称为黑点和白点。对于点分树中的每个白点（黑点），我们找到它的祖先中最近的一个白点（黑点）作为它新的父亲，这样就能得到两棵全由白点组成的树和全由黑点组成的树（因为有且仅有一个白点和黑点找不到同色的祖先），它们分别为原树切分得到的两棵树的点分树。
• 反过来再考虑，如果我们把两棵树通过一条边 连接起来，我们怎样把原有的两棵点分树合并起来，并且保持原本点分树中的祖先后代关系呢？可以发现，我们只要把 到所在点分树根节点的路径以及 到所在点分树根节点的路径按任意顺序归并起来即可。
  考虑树形DP。之前的结论意味着，我们只需要关心树的根节点在点分树中的深度。因此设表示对的子树进行点分治，并且在点分树中的深度为的方案数。把的儿子的DP数组合并上来时就有
  直接实现是的，预处理的后缀和就不需要枚举了。每次合并的复杂度是两棵子树大小的乘积，因此最终的时间复杂度为。

C、无向图定向

• Easy-3
• 答案 = 最小染色数 -

D、求和

先进行一些化简。
令

令
那么

E、棋技哥

• 搞你一波心态!

F、社团管理

• 决策单调性
• 类似整体二分转移

G、火山哥周游世界

• 考虑一下虚树和最远点？

H、火山哥的序列

• 我们从大到小考虑每个数 考虑每个数在什么时候能作为最大的
• 首先找到是这个数的所有倍数的数,假设位置是,那么显然还剩着(即),剩着,还剩着 (即),这些都是可能的
• 考虑一下我们实际上每次相当于删一个区间状物
• 用一个线段树维护每个点为左端点的时候最远删到了哪，以及还剩多少个区间没有被删即可。

I、N门问题

• 贪心地让每一步中正确的门的概率最小、每次打开概率最大的门、每次打开概率最小的门，这些策略都是错误的，枚举一些N=、的情况大概可以感受到
• 事实上，通过归纳法可以证明，无论打开了哪扇门，A选择的那扇门在门打开之后都会变成全场唯一概率最小的门。
• 通过这一结论我们可以把问题转成类似一个序列操作问题：
• 一开始有个球一起放在序列头，有一个是正确球。
• 每次从序列头的所有球中随机抽一个，然后可以丢弃剩下球中不是正确球的任意一个，然后把他抽的球单独地放在序列末尾
• 可以感受到，当足够大时，一定可以通过控奇偶性让必败(这也可以坑到只观察序列前三项而认为序列单调递增趋于的选手)
• 然后可以根据这个写一个，表示剩个球，第一堆有个球，正确球在位置，这种情况下获胜的概率 发现当的时候就有让必败的策略了
• 所以其实提前算完了小数据，大数据直接输出就行
• 于是又在外边套了个无聊的数论模型

  J、简单字符串

• 考虑一下我们肯定会切在Lyndon分解上

串

• 对于字符串，如果的最小后缀是他本身，那么是串。
• 为串等价于本身是其循环移位中最小的一个

我们可以将任意串划分成，其中都是串，这一形式被称为的串划分

存在性：初始时每段一个字符。不断地将相邻两段合并。
唯一性：若有两种方案，取第一次不同的位置，设，令
则