Warning: session_start(): open(/tmp/sess_44e15d734944c75c30675bcb6a324450, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/6/6a0f3843c5ea426c08feea4e44f84973.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 个人总结 ======
===== 陈铭煊 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 =====
考完计网再补，走了