关于本题树上版本
查看原帖
关于本题树上版本
416578
TDoG_W楼主2024/1/27 20:52

RT,前段时间讨论了积木大赛、均分纸牌的树上版本,颇有收获,所以今日来讨论这题。

形式化题意:给一棵树以及权值 pp,每个结点有权值 aia_i 和 bib_i,问有多少对 aia_i相同的结点之间的树上路径(包括这两个端点)存在至少一个结点满足 bi≤pb_i \leq p。数据范围与原题相同。

是否有时间复杂度符合这个数据范围的解法?目前感觉树上差分 + 树形 DP 可解。

2024/1/27 20:52
加载中...