本题是典型的树上合并背包,复杂度上限应该是O(np)O(np)O(np),然而大多数题解写的代码复杂度上限是O(np2)O(np^2)O(np2)。本题数据较小,都能通过本题,希望管理员在题面上提醒下通过本题后注意下自己的代码复杂度
正确写法
for(int i=siz[u];i>=0;--i) for(int j=siz[v];j>=0;--j) …… siz[u]+=siz[v]