这次比赛打的好，但又不好，200pts，rank4，但原本可以360pts的
T1
每一条边减去端点贡献，最小生成树即可
T2
从小到大枚举花瓣数，然后对于每一列记录前四大的，防止不能转移，然后直接跑即可
赛时打了一个线段树，被卡常+卡空间，hahaha
T3
暴力，先分解质因数，由于\(\varphi(p^k)=(p-1)p^{k-1}\),那么就可以对于每一个数，记录它的每一个质因子出现了多少次，每一次乘就对于质因子累加，而且由于\(2*3*5*7*9>600\),所以最多又4个质因子，可以看成常数，然后就可以\(O（1）\)更新答案，然后就直接\(O(nq)\)即可
赛时被shaber出题人用\(1e8+7\)给爆掉了
T4
这是一个究极抽象的做法
我们把它分成两部分来讲
part 1
如何求一个节点和特定的子树内的所有节点的距离和
这个可以用线段树，每次dfs到了一个点就对应在线段树中更新，然后用dfs序代表节点，然后直接查询区间和
part 2
回到原题，由于上面的，我们只需要求出一个满足条件的点即可，对于有另一个子树的，就可以根据\(dep_i+dep_j-2*dep_{lca_{i,j}}\),而lca就是两个根的lca，直接统计即可
先考虑两个有并的情况，这就只用考虑一颗子树的情况
我们先考虑从一个点x到他的一个儿子y会产生的变化
显然，\(ans=ans-siz[y]+other\)
我们要这个ans最大
首先，把树重链剖分，那么重心一定在根所在的到底的重链上，因为这样走，就能保证siz尽量的大，而如果有两个大小相同的子树，那么就不会再向下了，所以不会出现走到劣的情况
由于子树大小是递减的，而其他的点的数量是递增的，所以可以二分，每次查\(other-siz[y]\)是否大于0，这样就找到了一个点
而两颗子树的，必定只有两个子树和子树根之间的路径可能会有重心
我们分析一下，设两个子树的大小为x,y
那么往x那边偏移的贡献就是\(siz[y]-siz[x]\)，那么重心就一定会在大小较大的子树内，因为上面的要尽量小于0，那么就可以像上面那样做，而other加上小子树的大小即可
标签：子树,16,dep,2023.12,lca,other,即可,siz,模拟 From： https://www.cnblogs.com/longzhaocheng/p/17904932.html