CF1394D Boboniu and Jianghu *2800
- Tag： dp
- 提交记录：Submission #212971850
树上链相关组合优化自然考虑 dp，影响子树对父亲的贡献的唯一因素在于 \((u,fa_u)\) 向上还是向下，考虑将其放入状态里，设 \(f_{u,0/1}\) 表示以 \(u\) 为根的子树，\((u,fa_u)\) 向上/向下时子树内的 \(\sum a_i\)。
进一步地，考虑转移的贡献，容易发现对于任意 \(v \in son_u,b_v \not=b_u\)，边的方向已经固定，可以直接加进贡献里，而 \(u\) 对答案的贡献为经过它的链的条数乘上 \(a_u\)，而条数等于 \(\max\{in_u,out_u\}\)
，所以直接一开始默认 \(b_v=b_u,(u,v)\) 全部用 \(f_{v,1}\) 的贡献，枚举 \(in_u\)，每次把最小的 \(f_{v,0}-f_{v,1}\) 加上即可。
由于要对 \(f_{v,0}-f_{v,1}\) 排序，总复杂度 \(O(n \log n)\)。
- 总结： 权值二选一算贡献（\(f_{v,0/1}\)）可以用类似技巧。