关于做法的疑问
  • 板块P2195 HXY造公园
  • 楼主Guagua111一只蒟蒻
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/8/29 13:24
  • 上次更新2025/8/29 13:36:01
查看原帖
关于做法的疑问
937859
Guagua111一只蒟蒻楼主2025/8/29 13:24

正在做这道题,被另一个 OJ 的老师放在了并查集的题单,还不了解树的直径。我去看了看题解,发现大家都是用两次 dfs 先把直径求出来再操作的。我就有一个问题:能不能我直接整一个类似带权并查集的东西,用 dis[i]dis[i] 表示以 i 为根的树的直径。然后我就不求直径,在他最开始给出图的时候有两个节点 u, v 直接 merge(u, v),然后按照公式更新他们的直径。用这种方法替代题解里的 push 完节点再跑树形 DP,可不可以

2025/8/29 13:24
加载中...