A. Surprise me

直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。

于是可以套用莫比乌斯反演。

最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\sum \limits_{i=1}^{\frac{n}{T}}\sum \limits_{j=1}^{\frac{n}{T}}\varphi(i*T)*\varphi(j*T)*dis(p_{i*T},p_{j*T})$。

然后我的思路就偏了。

为了统计$dis(i,j)$，我把$i$与当前分治点的距离放到了对应的下标上。

用到了与$normal$一题类似的点分治做法，然后还得打个任意模数$ntt$。

复杂度有点奇怪，但是随机数据跑的挺快的（仅指能在8s内跑完）。

一个简单的解法是直接将$dis_{i,j}$拆分为$dep_i+dep_j-2*dep_{lca}$。

于是只要构造虚树就可以直接进行子树归并$dp$。

B. 过河（river）

考虑第一步送走的猪（不妨称之为猪王），一定满足是三元组的交集，否则一定无解。

将猪王从三元组中提出后，所有的猪形成二元关系。

发现一个结论是方案是否成立与原图删掉两个点后是否可以奇偶染色有关。

考虑一个方案，先将猪王运到河对面，接着不断运黑猪到河对面，之后运猪王回来，不断运白猪到河对面。

之后运一只猪王子到河对面，带猪王回来，再运一只猪公主。

然后就可以疯狂运大黑猪过去了，最后一手把猪王运回去就可以团圆回家过年了。

因为已经删掉了猪国王，还有两个特殊的猪分别是猪王子和猪公主，所以问题转化为删掉任意两个点和猪国王之后原图是否可以奇偶染色。

题解的做法又很神仙。

考虑枚举删掉一个点，然后直接进行DFS。

定义奇边为能形成奇环的非树边，偶边同理。

删掉另一个点后原图不含奇环，也就是可以奇偶染色的条件是：

1.该点被所有的奇边跨过。

2.不存在一条奇边和一条偶边，满足奇边和偶边均由这个点的一个子树上的点连向这个点的祖先链（对于这种情况，可以跨过该点直接形成奇环）。

对于前者，直接通过树上差分打标记修改。

对于后者，不妨直接维护两个追溯数组，表示每个点由它的子树最早可以追溯到的dfn值。

因为DFS树上只有返祖边，dfn值的大小与深度是有关系的，然后就可以进行判断了。

C. NPIO 十合一

提答题。

有意思的大概有：

1.求1e9个点，1e9条边的生成树边权总和（已知模998244353意义下的结果）

因为只多一条边，直接枚举替换掉的边的边权，然后和模998244353意义下的样例拟合，拟合上后模1e9+7就好了。

正解是根据该随机数的生成有逆元，树的生成方式较简单，直接反向推回去尝试替换。

2.求1e9个点形成的树，每个点的子树大小。

同样利用逆元。倒着推回去。size数组开不下。

因为数据是随机的，所以编号大的点size并不大。

所以对于编号小的点和编号大的点分别用int和short存下。

3.随机数据，维护最多1e9个元素的堆。

因为数据随机，堆中同时并没有很多元素，所以直接用std的暴力跑就好了。

4.随机数据，1e9个数，插入每个之后求中位数。

一个指针加上一个桶，指针维护前缀和。

因为数据随机，所以中位数的变化并不多。

5.随机数据，1e7个点，1e9条边，求每个点双中点的编号的和。

因为数据随机，点数边数差距过大，最终只有两个点双。

因为数据生成的性质，奇数偶数分别形成点双。