QOJ #7509 01 Tree
翻转深度为奇数的点的颜色，将操作变为交换相邻的 \(\tt 0\) 点和 \(\tt 1\) 点。
对于每条边考虑，其施加操作的次数为 \(s\) 与 \(t\) 在其子树中 \(\tt 1\) 的个数差的绝对值。
所以对于串 \(X\)，令 \(q_{X,e}\) 为边 \(e\) 较深一端的子树中 \(\tt ?\) 的个数，\(q_{X,S}\) 为总的 \(\tt ?\) 的个数；
令 \(v_{X,e}\) 为边 \(e\) 较深一端的子树中 \(\tt 1\) 的个数，\(v_{X,S}\) 为总的 \(\tt 1\) 的个数，有答案为：
\[\sum_{e\in E}\sum_{a=0}^{q_{s,e}}\sum_{b=0}^{q_{t,e}}\sum_{c=0}^{q_{s,S}-q_{s,e}}\sum_{d=0}^{q_{t,S}-q_{t,e}}[a+c+v_{s,S}=b+d+v_{t,S}]|a+v_{s,e}-b-v_{t,e}|\dbinom{q_{s,e}}{a}\dbinom{q_{t,e}}{b}\dbinom{q_{s,S}-q_{s,e}}{c}\dbinom{q_{t,S}-q_{t,e}}{d}
\]