洛谷 P4244 [SHOI2008]仙人掌图 II(圆方树+单调队列)
题目链接题意求仙人掌直径思路圆方树,树形dp,dp[u] 表示以u为根节点最长链原点到原点,正常dp原点到方点,正常dp方点到原点,圆点各点加上方点父亲节点应该是一个环,然后对这个环用基环树求直径(单调队列),但是注意复制序列时方节点父亲并没有被考虑,判断一下。建树加粗是方点,方点的儿子之间距离按遍历顺序考虑,而不是图上的简单路径权值和考虑序列应该如图b是实际存在但不...
原创
2019-10-05 17:26:18 ·
259 阅读 ·
0 评论