Description：

给一棵树，每个点是黑点或者白点，我们称黑点个数等于白点个数的路径为好的路径，问有几种方案选择一个区间使得两端点标号都在这个区间的好的路径多于两个端点标号都不在这个区间的好的路径。

$1\leqslant n\leqslant100000$

Solution：

首先发现合法的区间具有单调性，也就是说如果 $[l,r]$ 合法，那么所有包含 $[l,r]$ 的区间都合法，那么我们就可以对于每个 $R$ 求出来一个极小的 $L$ 使得 $[L,R]$ 不合法，那么这个 $R$ 的贡献就是 $L-1$ ，设 $A$ 为两个都在区间内的答案， $B$ 为都不在， $C$ 为一个在一个不在，那么 $A+B+C=sum$ ，由于 $A>B$ ，那么 $2A+C>2B+C$ ，然后有： $$ 2A+C=\sum_{i=l}^rf[i] $$ $f[i]$ 代表一个端点是 $i$ 的合法路径个数， $sum$ 表示所有合法路径个数，他们都可以用点分治来统计， $f[i]$ 只要考虑 $i$ 和之前的子树形成的路径数，然后正反各扫一遍子树就行了，最后双指针即可求出 $L$ 。

Code：

没有代码