退役之后暂时还没有回去搞文化课，让我们vp几场cf吧
1A 考虑我们要最小化最后一个人到终点的时间，所以最优解是每个人一起到，每个人坐 d 分钟的公交，最优解是公交来回接送每个人d的距离，二分 d 的大小，然后模拟一遍判定是否合法即可。
1A 考虑如果存在两个匹配是不相交的，那么我们把它交换成相交的，肯定会更优，所以所有匹配之间两两相交，因为没有环，只能是都交于一点 存在一组交于一点的合法的匹配的条件是：按照每个点属于的子树给每个点染一个颜色之后，存在一个匹配使得相邻两点颜色不同
必要条件是不存在一个点出现超过⌊n2⌋次（和TCO正交变形词有些相似） 正交变形词一题是二分图，用Hall定理可以证明。 这题是一般图匹配，我们用Tutte定理试一试，Tutte定理是说， ∀U⊆V 点集 V−U 的导出子图有不多于 |U| 个连通块有奇数个点（和Hall定理一样必要性显然，所以其实挺好记0.0） 然后如果 V−U 有两个不同的颜色它就联通了，从而我们只需要考虑 V−U 只有一个颜色的情况，显然是这个颜色的个数不能超过sum / 2个
于是其实满足条件的点就是重心，答案就是所有点到重心的距离，多个重心的话显然答案一样
题解的做法要简单多了0.0 贪心考虑每个边，如果能过这个边，子树里的点肯定是尽量过这个边的，所以答案就是 ∑umin(sz[u],2∗k−sz[u]) 开始想到这样的性质之后没怎么想证明0.0
5A 考虑求出一个dfs树之后，割去的显然有一条dfs树上的边，要满足T在它的子树中，O(n)枚举这条边，现在有三种可能： 1.没有割第二条边：条件是没有非树边从子树里连出来 O(nm)处理出过每个树边的返祖边的个数 2.第二条边是非树边：条件是只有一条非树边从子树里连出来，一样O(nm) 3.第二条边是树边，条件是它在第一条边的子树中，并且T不在它的子树中，并且经过它的返祖边集合和经过第一条边的一样 我们O(nm)处理的时候给每个返祖边赋一个随机的unsigned long long的权，然后xor起来得到每个树边对应的集合的hash值即可
赛后订正
区间询问Huffman Coding其实挺难的，因为求Huffman Coding 必须要跑一边那个算法
我们必须要对每次询问跑一边那个算法，log是不太可能了，能不能根号呢
一个经典的制衡的结论是，若干个东西加起来是 n 的话，那么不同的东西的个数是O(n√)的，因为大于 O(n√) 的只有 O(n√) 个
所以区间内每种数字的『出现次数』只有 O(n√) 种情况，我们把出现次数相同的节点并到一起处理，然后用莫队算法求出区间内每种出现次数的个数即可。
赛后订正
因为子串个数是 O(n2) 的，我们肯定要把它降到 O(n) ，考虑如果a出现了若干次，并且这若干次之后的字母都一样，那么a+c一定可以替代a
从而只有后缀树上的节点单词是有意义的
但是在后缀树上处理某一个S的子串s出现了两次还是困难的，我们需要再固定一些东西
考虑利用已经算过的信息，每次在前面加一个字母，计算一个子串是它的前缀的情况，然后再max上它所有后缀的答案
max上所有后缀的答案只需要在计算完S之后顺着trans边，update所有trans的答案即可
计算一个子串是它的前缀的情况其实就是找它的第一个祖先，使得这个祖先在不是它的前缀的地方出现了，任意去它的一次出现位置[l,r]，也就是说祖先（长度为len）的子树里存在一个[l + 1, r - len + 1]的后缀单词节点
主席树维护子树和，往上倍增找这个祖先是O(nlog^2n)的
如果树链剖分之后，在主席树上二分，那么是O(nlogn)的
主席树要稍微开大到N * 20，就是说可能是N * (log + 1)
2016-08-13
2016-08-17
大概是三十几名了，三题都有思考的时候不够冷静的地方，犯了一些错误，C题没有注意没有dfs到的点，所以TLE了很多发，希望退役选手早日康复
