关于本题复杂度的问题
  • 板块P1272 重建道路
  • 楼主yzhang
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/10/15 19:34
  • 上次更新2023/11/5 10:42:54
查看原帖
关于本题复杂度的问题
37881
yzhang楼主2020/10/15 19:34

本题是典型的树上合并背包,复杂度上限应该是O(np)O(np),然而大多数题解写的代码复杂度上限是O(np2)O(np^2)。本题数据较小,都能通过本题,希望管理员在题面上提醒下通过本题后注意下自己的代码复杂度

正确写法

for(int i=siz[u];i>=0;--i)
    for(int j=siz[v];j>=0;--j)
    	 ……
siz[u]+=siz[v]
2020/10/15 19:34
加载中...