====== 个人总结 ======
===== 陈铭煊 Max.D. =====
这一周的话主要打了两场牛客的比赛，其余的话没有学习知识
===== 龙鹏宇 Hardict =====


===== 肖思炀 MountVoom =====

这个人已经死在计网实验了
====== 本周推荐 ======
===== 陈铭煊 Max.D. =====
来推荐一道方法很神仙的题目，[[https://ac.nowcoder.com/acm/contest/5555/B|链接]]

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

===== 龙鹏宇 Hardict =====

**一道点分治**

[[https://www.luogu.com.cn/problem/P3085|链接]]

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

**题意**

一棵树,树上每条边黑或白色,统计有多少个$(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]组合$
===== 肖思炀 MountVoom =====

考完计网再补，走了