description
给定一棵有根二叉树，每条边有一个字符或特殊字符，特殊字符可以和任意字符相等。如果这棵树树根到每个叶子结点经过边的字符构成的字符串每个重排后都相同，则这棵树是可以重排的。每个字符的重排度为其在所有可能的使树可重排的安排特殊字符的方案中该字符出现次数的最大值，记做 \(f(c)\)。现在字符集使小写英文字母，权值 \(w(c)=c-\texttt{a}\)，即 \(\texttt{a}\) 的权值是 1，\(\texttt{b}\) 的权值是 2，以此类推。
有 \(m\) 次操作，每次将树上一条边的字符修改（可以改成特殊字符）。每次操作后判定当前的树是否可以重排并求 \(\sum f(c)w(c)\)
- \(n,m\leq 1.5 \cdot 10^5\)
solution
先考虑判断一棵有根二叉树可以重排的充要条件。
首先所有叶子节点必须深度一样，否则字符串长度不同，一定不相等。
再考虑叶子结点深度相同的情况，思考一下发现要满足对于所有的点 \(u\)，\(\sum f_{u,c} \leq D_u\)，其中 \(f_{u,c}\) 为以 \(u\) 为根的链中，字符 \(c\) 已经出现（不包含特殊字符）的最大次数，\(D_{u}\) 表示 \(u\) 到底的深度。
要算的东西就是 \(\sum w(c)(D_{1}-(\sum\limits_{d} f_{1,d})+f_{1,c})\)。
于是一个 \(O(\Sigma n+q(\Sigma +n))\) 的做法就有了。
来优化这个做法！
还没有使用到二叉树和所有叶子节点都深度相同的性质。而我们的操作是往上跳，复杂度和树的深度有关。树的深度最大的时候是树长成一条链，这时候跳的复杂度是 \(O(n)\) 的。我们考虑如何加速处理链的情况。
当 \(u\) 向上跳一条边时，\(D_u\) 增加 1，\(\sum f_{u,c}\) 最多也增加 1。所以如果 \(u\) 满足条件，则链顶一定满足条件；如果 \(u\) 不满足条件，则链底一定不满足条件。链底满足条件可以推出 \(u\) 满足条件；链顶不满足条件可以推出 \(u\) 不满足条件。因此我们只需要管链底链顶就行了。
回到二叉树上，如果一条链都是只有一个儿子的节点（或叶子节点或根节点），那么只需要管链底和链顶就好。也就是只保留有两个儿子的节点和根节点和叶子结点。
又因为所有叶子结点深度相同，这样树的高度最多就是 \(O(\sqrt{n})\) 了。
下面的这棵树保留上述点后可以把深度卡满：
综上，时间复杂度 \(O(n\Sigma+q(\sqrt{n}+\Sigma))\)