P5642
【树论典题】P5642 人造情感（emotion）
P5642 人造情感（emotion） 随便挑点杂题做/kk。 乐。 不会做这个题，我难道还不会做 CF856D Masha and Cactus。 先考虑后者怎么做？ CF856D Masha and Cactus 乐。 考虑在 \(LCA\) 上挂很多个 chains. \[s_u = \sum ......
P5642 人造情感（emotion）
# P5642 人造情感（emotion） [洛谷：P5642 人造情感（emotion）](https://www.luogu.com.cn/problem/P5642) ## Solution 子问题：[HDU5293 Tree chain problem](https://acm.hdu.ed ......
洛谷 P5642 - 人造情感（换根 dp）
想起来很轻松，写起来很酸爽的套路题。 默认以 $1$ 为根。先考虑怎么算单个 $f(u,v)$，我们定义一个连通块的权值为从该连通块中选出若干条点不相交的路径，选出的路径的权值之和的最大值。那么显然 $f(u,v)$ 就是整棵树的权值 $-$ 挖掉 $(u,v)$ 这条路径后各个连通块的权值之和。显 ......