来推荐一道方法很神仙的题目，链接

比赛当场想破脑袋都没相出来，结果是利用了数据产生的随机性+容斥原理。

一道点分治

链接

计数时没有用一般的容斥,而是直接计数

题意

一棵树,树上每条边黑或白色,统计有多少个$(u,v),s.t: \exists t \neq u,v,t在(u,v)简单路径上,且(u,t),(t,v)分别黑白平衡$。黑白平衡是指黑白数量边个数相同

题解

如果考虑$(u,v)$单独黑白平衡,令$边权值:黑:1;白:-1$;黑白平衡即$dis(u,v)=0$

即为简单的点分治计数问题

但根据题目条件,说明以$r$为子树搜索时,$(x,y)$黑白平衡说明$dis(r,x)=-dis(r,y),\exists z 为x或y的祖先,s.t:dis(r,x/y)=dis(r,z)$

这其实可以在点分治搜索时判断对应点的$z$是否存在,但容斥计数会出现一定的问题

这题需要考虑全局:

$f[d][0/1]:表示,正在搜索子树距离根距离为d且z存在/不存在的点的个数
g[d][0/1]:表示,之前搜索过距离根距离为d且z存在/不存在的点的个数$

显然$f[d][0]与g[-d][1]组合,f[d][1]与g[-d][0/1]组合$