就在刚刚同机房大佬看到了我的贴,经他指点,此贴已解决。
首先,逆着循环是这样的:
```cpp
siz[u]+=siz[v];
for(int i=min(k,siz[u]); i>=0;i--){
for(int j=min(i,siz[v]); j>=0;j--){
......
}
}
```
然鹅,这样的 $f[u][i-j]$ 很可能是个无效状态。而正着枚举刚好能避免无效状态转移。
所以只需判断 $f[u][i-j]$ 是否有效即可。
```cpp
int sz=siz[u];
siz[u]+=siz[v];
for(int i=min(k,siz[u]); i>=0;i--){
for(int j=min(i,siz[v]); j>=0;j--){
if(i-j>sz){
continue;
}
......
}
}
```
by _Cheems @ 2023-08-08 07:41:56
这个帖子还是留着罢,给那些和我一样逆着循环超时却不知道错哪的人看。
by _Cheems @ 2023-08-08 07:44:07
\bx
by 233333qz @ 2023-10-28 14:45:58
你这是可以的,其实只要把siz的更新放到for后面就行了
by diandian2020 @ 2023-11-17 21:32:27