Day 11

一口毒奶。。。今天神TM又是正睿OI可还行吧？？？
今天的评测用上了长沙一中机组搭的OJ，不过似乎出了不少锅？
特意去搜了一下今天的题目名字都是来自WestLife的歌名

T1 Last Mile of the Way

这个题面。。。可以进迷惑题面大赏了233333
我和某czh dalao一开始都以为这个题是要求一个子树中所有大小大于k的节点点权之和，结果完事了是个树上泛化物品背包？？要不是我最后推了一下样例我的树状数组和czh的树形DP可能就交上去了
不过考虑到本题的泛化物品背包的物品数和范围可达到5000，普通股的O(n^3)的泛化物品背包的合并方式是稳稳地超时了。
考虑一下怎么优化。我们原先是对于每个节点将其所有孩子进行泛化物品的求和。我们考虑如何把这部分的复杂度减下去。我们注意到如果在一条链上，每个父亲只比他的孩子多出一个物品，即它本身。那么如果在一条链上我们就可以只花费O(k)而不是O(k^2)的复杂度去转移。我们考虑如何将其推广到树上。我们可以把一个节点的子树分成一条链和其他孩子，我们对这条链进行O(k)的转移，对其他部分暴力统计即可。但是这条链要选择哪一条呢？事实上上面我们把一棵子树拆分成链和其他节点就已经提示了我们———我们可以使用树链剖分中的轻重链思想，每次对重儿子使用O(k)的合并，其余孩子直接暴力合并即可。这样能够保证我们每次O(k)合并时一定合并的是较多的节点，暴力的是较少的那一部分，这样使得整体的时间复杂度大为降低。由树剖的时间复杂度证明我们可以知道这么做可以将合并的复杂度降至O(n \log n)，总复杂度为O(nk \log n)

T2 Reason for Living

其实这个题我还是没有看懂。。。在听过zhw dalao的讲解大概能懂一点了【趴
题目大意是给你一个无向图，每次尽可能多的删除一个生成树（森林）中的所有边，求图中每条边是在第几次被删掉的。
时间复杂度正确的正解所在的网站似乎挂掉了，只留下了一个O(m \log m⋅α(n))的解法，用的是二分+压空间并查集。但是说实话吧，其实咱也完全没看懂这个题解，所以在zhw dalao的指导下打了一个理论O(m^2)但实际卡卡常完全能过的算法。我们注意到我们使用最直觉的算法，即每次尽可能将所有边加入到删掉的边当中，每次至少可以删除一条边。我们只要保证我们在找边的时候不要重复访问到已经被删除的边即可保证时间复杂度只有O(m⋅α(n))。再加上快读快输register等玄学常数优化便可卡过此题。

T3 World of Our Own

果然是正睿OI就会有xor么。。。
考场上推了半天的题。直觉告诉我这个破题肯定是有规律的，于是硬是手推到了26还是没找到规律。。。最后告诉我要序号-1才能找到稳定的，准确的规律？？？

for (int j = 0; j < 23; j++) {
    for (int i = 0; i <= n; i++) {
        if (i >> j & 1) a[i] ^= a[i ^ (1 << j)];
    }
}

证明看这里