这清华集训打得有点萎，这几天就来更一下题解好了。感想就不写了 代码写的比较惨，就不贴了
Alice和Bob又在玩游戏
关键词：SG函数，Trie的合并
题目描述
有个节点，条边（），构成若干棵有根树，每棵树的根节点是该连通块内编号最小的点。
Alice和Bob轮流操作（Alice先手），每回合选择一个没有被删除的节点，将及其所有祖先全部删除，不能操作的人输。
需要注意的是，树的形态是在一开始就确定好的，删除节点不会影响剩余节点父亲和儿子的关系。
比如： 这样一条链，号点是根节点，删除号点之后，号点还是号点的父节点。
假设Alice和Bob都足够聪明，问Alice有没有必胜策略。
对于的数据，，输入数据保证不会形成环，且每棵树的大小。
算法简述
这个题其实今年集训队作业里是有的，只是这里的数据范围大了一些。考虑用SG函数，表示以为根的子树的SG值。 这样直接搞的复杂度是，可以用来维护sg值和求mex操作，合并子树的时候可以用的合并。复杂度或
魔法小程序
关键词：高维前缀和
题目描述
有这样一段魔法的程序：（其中所有的数组下标从 开始，所有的除法的结果为整数，且向 取整）
定义数组 a[], b[], c[]
定义函数 魔法(x, y, z):
{
如果 a 的长度 == z:
返回 x >= y
如果 x % a[z] < y % a[z]:
返回 假
返回 魔法(x / a[z], y / a[z], z + 1)
}
定义函数 主程序():
{
读入 a[], b[]
令 c[] 的长度与 b[] 的长度相同，且 c[] 的每个元素均为 0
令 变量 i 从 0 循环至 b 的长度 - 1:
令 变量 j 从 0 循环至 i:
如果 魔法(i, j, 0):
c[i] += b[j]
输出 a[], c[]
}
这个程序目前十分低效（显然时间复杂度至少是平方量级的），无法快速完成百万级别的计算，但我们现在的任务不仅是优化它。
现在我们给出这段程序的输出，你需要完成一个“非确定机”的工作，给出一个可能的输入。
的长度不会超过 。 的每一个元素不会超过 。
的长度不会超过 。对 的元素的范围没有直接的保证，但是保证存在一个解 ，使得 的每一个元素的绝对值都不超过 。
和 都至少拥有一个元素。
算法简述
这个题第一眼看起来，解应该只有一个，因为可以解个方程算出来。再看一看，发现这个东西和的比较像，这其实就是一个高维的前缀和。就可以反过来搞，对每一维分开来求差分，最后就能还原出来了。要注意细节问题。
数据交互
关键词：树链剖分
题目描述
一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。每个数据交互请求都有一个非负的重要度，越重要的请求显然需要得到越高的优先处理权。此外，如果在某一个时刻存在一条非常重要（可以看作重要度无穷大）、且数据量巨大的交互请求，则所有被该交互经过的服务器都会优先处理这条交互并阻塞，从而导致其他通过这些服务器的交互出现延迟。
现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也很简单，在每一个时刻，只有可能出现下列二种事件中的一种：
- 在某两个服务器之间出现一条新的数据交互请求；
- 某个数据交互请求结束。 我们假设这些事件中的交互请求的数据量都足够小。
你的任务是在每一个时刻的事件结束后，求出：如果突然出现一条非常重要、且数据量巨大的交互请求，那么因其造成延迟的数据交互请求的重要度之和最大可能是多少？
算法简述
这个题的idea我感觉还是挺不错的。首先把每个边都拆出点来。每一次添加数据交互请求就相当于给路径上所有边点都减去权值，点点都加上权值。每次要求的答案就相当于这个树的直径。这样就变成了，链修改，求直径的问题，可以套用Qtree7的做法，搞链剖，维护最高点在每一条重链上的最长的路径。这个题稍稍有点繁琐的地方在于，一条路径上的点有两种，点点和边点交替出现，每次修改的时候，边点和点点的加的值正好相反。那么就可以在线段树上多维护一些信息，把起点终点是点点和边点的分开来维护，就可以了。
