看到异或求和，考虑拆位计算 $v+d(c,x)$ 的第 $k$ 位。不难发现它随着 $d(c,x)$ 每增大 $2^k$ 改变一次。

这启示我们对于每个点考察它对所有祖先的贡献。于是我们要做的第一步是树上差分，将一系列深度相差 $2^k$ 的祖先的差分值异或 $1$。

这个操作不能暴力做。考虑用一个桶对于每个 $i$ 记录某个点的所有祖先中，深度 $\bmod2^k=i$ 的点的差分值。但是这样子树需要向父亲贡献一个合并复杂度为 $O(s)$（$s$ 表示子树大小）或 $O(2^k)$ 的信息，取决于考虑子树内每个点对桶的贡献，还是直接使用子树的桶在对应位置相加。前者可以用树上启发式合并优化。

更好的做法是维护子树内可减信息的经典 trick（天天爱跑步）：

维护一个全局桶，子树跟处只需要记录自己关心的某个位置的值，在遍历子树前和遍历子树后的差，即可求得子树内对桶该位置的贡献。

我们令任一重心作为根，分类统计。

一棵树的重心要么是根，要么在重儿子内，换言之，在重链上。

那么每个子树的重心可以均摊 $O(1)$ 地从其重儿子子树重心开始向上寻找。

对于一整棵树去掉一个子树后剩余的连通块，分类讨论：

如果删掉的部分不在重儿子内，此时删掉的部分大小相同，剩下部分重心一定相同。所以我们只需要从小到大枚举删掉部分的大小，同时向上移动整棵树的重心，时间复杂度 $O(n)$。另统计出轻儿子子树内，某个大小的子树各有多少棵。

如果删掉部分在重儿子内，而删掉后重儿子仍然是重儿子，剩余部分的重心仍然在重链上，并且一定不比原重心低，只能是根。

否则次重儿子会成为重儿子。此时类似地统计出删除重儿子内某个大小的子树后重心是谁，以及重儿子内某个大小的子树各有多少颗。

给定一棵无根树，在树上选 $k$ 条路径，它们的并构成一个包含 $u$ 的连通块，要使连通块中包含的边的权值和最大。

一道纯粹的性质题。

首先，一棵树能够被 $k$ 条链覆盖，当且仅当它有不超过 $2k$ 个叶子。

这里必要性是显然的，至于充分性，构造任意一种所有叶子都被覆盖，每条边长度至少为 $1$ 的方案，如果树没有被完全覆盖，找出任意一条极长的没有一条边被覆盖的非空路径 $p$。显然 $p$ 的端点 $u,v$ 不为叶子，因为端点为叶子，意味着路径 $p$ 包含了叶子的唯一出边；而方案中所有叶子都被覆盖，意味着叶子的唯一连边也被覆盖，这与 $p$ 的要求矛盾。既然 $u,v$ 不为叶子，而 $p$ 极长，那么 $u,v$ 一定分别存在于两条覆盖路径 $s\to t,x\to y$ 上。此时我们调整方案，将这两条路径换成 $s\to x,t\to y$，原来被覆盖的所有边仍然被覆盖，而为被覆盖的路径 $p$ 被覆盖。因此我们不断进行这样的调整，这个过程一定会在有限步内结束。

其次，选择 $k$ 条链，构成的包含边权和最大的子图，一定是连通的。一个不连通的方案，通过上述调整方法可以使其变得连通，并且更优。也即我们只需要保证我们能够考虑到最优方案，并不需要注意我们是否考虑到了不连通的选链方案。

---

不难发现，包含边权和最大的连通块至少包含带权直径的端点中的一个，调整法易得。

鉴于正权树的带权直径的两个端点一定是叶子，问题形式变为，分别在以两个端点为根的树中，选择 $2k-1$ 个叶子，要求它们到根的路径的并形成的连通块包含 $u$，求连通块内边权和最大值。

抛开连通块包含 $u$ 的条件，进行一个简单的贪心——长链剖分（注意这里是划分边集，可能有出现在多个链中，而非像大多数树链剖分一样划分点集），然后选择最长的 $2k-1$ 条链构成该连通块。它的正确性也很显然，最优解必然可以表示为几个长链的并，否则一定存在某个长链，该方案只包含了这个长链的某个真子集，那么此时将这个长链并入该方案，不会使其产生新的叶子，却会使该方案的答案增加。每个长链恰含有一个叶子，也即我们能够选择最多 $2k-1$ 条长链。所以选择长度最长的 $2k-1$ 条长链一定不劣。

如果这样构造出来的方案不包含 $u$ 呢？我们需要做出一些调整。

第一种调整方法是只选长度最长的 $2k-2$ 条链，外加一条根到 $u$，再到 $u$ 子树内深度最大点的路径。

第二种调整方法是将 $u$ 的最近的在连通块内的祖先 $f$，不选 $f$ 以及它所在的长链中 $f$ 以下的部分，而是选择 $f$ 到 $u$，再到 $u$ 子树内深度最大点的路径。