T1「二分」
22分的暴力是枚举点集,然后发现dp[状态]时间和空间都承受不了
然后从另一方面考虑,题干说保证ans<=1e9那么很明显的表明了是二分,
首先k>0的一定是单调递增,那有负数呢?
冥冥中感觉这题不可能这么水,可能不保证单调,
然后就加了个三分,调了半天,总共用了两个半小时,以致后两个题都没调出来
考完听DeepinC大佬讲了一下为什么单调
先chk(0)一下,如果符合直接puts("0")
否则,在接下来二分的时候k<0的点集的贡献绝不可能再到s
所以对chk没有影响,故单调上升
T2「树状数组」「dfs序」
由于最后只是输出$X_1$,那么就很自然地想到用$X_1$表示其他的东西
那么对于新加的方程,会出现如下情况:$X_u+X_v=t$或$X_u+X_v==t-2*X_1$或$X_u+X_v==t+2*X_1$分开讨论
对于修改:可以发现每个w值的改变,只会影响其子树,而且奇数深度和偶数深度的贡献是相反的
将树转化为dfs序列,然后维护+x4-x3+x2-x1这样的固定形式,那么奇或偶直接取相反数即可