Opencup 2022.2.2
K
设 f_{u,i,w} 表示 u 子树内删掉 i 条边，u 所在连通块内点权和为 w 是否可以构造出来，复杂度 \mathcal O(nKR^2)
发现 i 固定时候其他连通块权值和都在 [L,R] 所以只有 R-L+1 个不同的值，因此 w 只有 O(k(R-L)) 个不同的值，这个做法是 \mathcal O(nK^3(R-L)^2) 的
bitset 优化以后变成 \mathcal O(nK^3(R-L))
引理：若 f_{u,i,w_1}=f_{u,i,w_2}=f_{u,i,w_2} ，且 w_1<w_2<w_3 且 w_3-w_1\leq R-L ，那么将 f_{u,i,w_2} 设为 0 不影响答案。
证明：设 u 所在连通块总点权和设为 W ，如果使用 (u,i,w_2) 这组构造，换成 (u,i,w_1),(u,i,w_3) ，则权变化为 W-(w_2-w_1) 或 W+(w_3-w_2) 。由 w_3-w_1\leq R-L 知这两者必然有至少一个合法，因此可以不考虑 (u,i,w_2)
由引理知 w 的 \mathcal O(K(R-L)) 种取值里只需要保留 O(K) 个为 1 的量，因此复杂度优化为 \mathcal O(nK^3)
I
建树，然后发现每个修改会导致树上一条 P_{u,v} 的链被删除，其中 u, v 为祖先后代关系
对询问和修改的时间顺序分治，当前在处理 [L,R] 内的修改，设删除的对是 u,v , 把所有 u,v,fa_u 建虚树（祖先后代链不涉及LCA），然后用线段树维护新增的数对，复杂度 \mathcal O((N+Q)\log^2(N+Q))