RT,前段时间讨论了积木大赛、均分纸牌的树上版本,颇有收获,所以今日来讨论这题。
形式化题意:给一棵树以及权值 ppp,每个结点有权值 aia_iai 和 bib_ibi,问有多少对 aia_iai相同的结点之间的树上路径(包括这两个端点)存在至少一个结点满足 bi≤pb_i \leq pbi≤p。数据范围与原题相同。
是否有时间复杂度符合这个数据范围的解法?目前感觉树上差分 + 树形 DP 可解。