晚上回来剩一个小时，cv了e题，干了一个小时的g，差一口气，虽然没a掉，但是我还是想写下题解，记录一下我的g杀马特解法

e题我某次在刷一场div3的d还是e的时候，读题读假了，读成了今天的e题版本，然后我想出了正解，没地方交，后来网上搜的时候搜到了ecnu里有这题 https://acm.ecnu.edu.cn/problem/3451/，我就交了一次

今天上号一看，直接cv了

E题
判定是否有解很简单，只需要众数大于n/2就是无解的
接下来考虑字母构造解
把所有下标按字母分组，组与组之间按频率从大到小排序
然后从排好序的组中的下标取出来
遍历所有的组，除了第一组匹配末尾，剩下的组都匹配前面剩余的即可


G题
多次查询树上所有点到一条链的距离之和
普通的树形dp能求出一个子树中所有点到该点的距离之和
换根dp能求出以每个点为根时，所有点到这个点的距离之和  https://ac.nowcoder.com/acm/contest/28260/F


看这张图，路径2-3
1管着8，2管着4和5，3管着6和7
我们刚刚说了，如果要求的是，1管着 2,3,4,5,6,7,8很好求
现在不让1管2和3子树了，怎么办？不让管就不管了呗
我们要想办法快速统计一条链上的权值，那么很明显肯定是lca配树上前缀和
当一个点接管的那一刻，他的父亲就不应该管他下面的点了
即先把每个节点设为直接管理整个子树的权值，然后减去 从父亲为根角度看，接管这颗儿子整棵子树的权值
这是一个差分的过程，我是在这题第一次遇见的 https://www.luogu.com.cn/problem/P5305
这些东西都可以在换根的过程中统计出来
最后查询的时候，如果lca不是1，那么还要累加一下从lca为根视角下，管理fa[lca]整棵子树的权值
最后的最后，除了1，其他的节点的权值其实都是不完整的，都差分过父亲的一个值，还要加回来（我就是在这里翻车了，赛时没加上)