洛谷P4781 题解公式 inline int FastPow(int x, int y) { if (y == 1) return x; if (!y) return 1; int tmp = FastPow(x, y >> 1) % mod; return tmp * tmp % mod * (y & 1 ? x : 1) % mod; } inline void Lagrange() { go(i, 1, n, 1) { up = down = 1; go(j, 1,

Read More

题目传送门 性质 删除重心后所得的所有子树,节点数不超过原树的1/2,一棵树最多有两个重心;2.树中所有节点到重心的距离之和最小,如果有两个重心,那么他们距离之和相等; 两个树通过一条边合并,新的重心在原树两个重心的路径上; 树删除或添加一个叶子节点,重心最多只移动一条边; 一棵树最多有两个重心,且相邻。 思路 如果找到只有一个重心,那么直接删一个重心的直连边然后加回去就好了。 如果找到两个重心,那么在其中一个重心上找到一个直连点不是另一个重心,删除连另外一个就好了。 如何求树的重心? 先任选一

Read More

原题链接 https://codeforces.com/contest/1406/problem/D 思路 样例中a=2,-1,7,3; 差分为-3,8,-4; 设(b[1]=x)+(c[1]=y)=a[1]; ∵b[1]=c[2]>=…>=c[n] x+(y-3)=(x-1)+(y-2)=(x+1)+(y-4)=…=a[2] ∴b[2]=x c[2]=y-3为最优解 其他的解都会导致b[n]或者c[1]变大 使最后答案不是最小 即:差分>0时,将差分的

Read More