标签：迁跃 right 题面 max T2 text rightarrow CW left

题面

似乎有原题, 但是很偏
挂个 pdf
题面下载

算法

一眼树形 dp
然而考场上没想出来
很显然有一个式子
令 \(f_u\) 表示从 \(u\) 进入子树, 再通过迁越回到点 \(u\) 的最大价值
则有

\[f_u = \sum_{exist\text{ }u \rightarrow v}^{(v, w)} \max (f_v + w - k, 0) \]

但是我们并不一定要回到根(考场上想不出来的原因), 于是枚举最后停止的点 \(t\)
于是答案的式子为

\[\max\left\{f_t + \sum^{(u, v, w)\text{ }on\text{ }the\text{ }list\text{ }from\text{ }1\text{ }to\text{ }t}_{u \rightarrow v} \big [ f_u - \max{\left(f_v + w - k, 0 \right) + w \big] }\right\} \]

意思就是统计不在这条链上的子树的贡献和链的总边权

代码

dfs 回溯时转移即可

总结

多见见这种类型的题

标签：迁跃,right,题面,max,T2,text,rightarrow,CW,left
From： https://www.cnblogs.com/YzaCsp/p/18487105