最小割

线性筛，隐式莫反（构造f函数的时候用的），分块，O(n)预处理，O(sqrt(n))查询
其中定义f(x)=(d|x)d*miu[x/d]，不难证明f函数的积性，之后有假设1<=i,j<=n，ans=(1<=x<=n)(n/x)*(n/x)*f(x)（莫反的枚举变量交换一下），询问分块就好了。
不难证明，F(x)=(d|x)f(x)=x（莫比乌斯反演公式可证）
所以也可以杜教筛求f函数的前缀和，每次询问O(n^(2/3))，预处理O(n^(2/3))。
这真是智障，我用莫比乌斯函数求出来了欧拉函数- -

回复 @～殘觷～ :
%%%%%%%%%%%%%%%%%

喜闻乐见，板子写错了还能A题QAQ。记得特判，第一问答案为1时输出两个n

在Linux下如果不强转貌似不会转，然后就WTE了

偷懒不成惨入坑，膜拜神犇余华程。
周期暴力打表好，打表不要打得少。

身败名裂......

由于蒟蒻没有博客，所以没办法放题解
请意会灰色线的位置，灰色线的方程是y=x+1。
没有题解，只有标程，证明请类比 原题的题解
有人搞出来最后一问吗……

有一种神奇的流叫做tb_kp流......

回复 @～殘觷～ :
没听说过

回复 @riteme :
感谢神犇的知道，NOIP后我才知道树上的链修改点求值可以变成点修改子树求和。

回复 @AntiLeaf :
%%%%

%%%%%%%

回复 @～殘觷～ :
显然只有黑点和白点有冲突，黑白染色之后是一个二分图，然后不还是最大权独立集么= =

你有信仰吗

回复 @AntiLeaf @Go灬Fire :
最大流 = 最小割 = 最小点权覆盖 = sum - 最大点权独立集
拿到的最多就要独立的最少

无聊写了个快读

回复 @Go灬Fire :
话说这不就是二分图最大权独立集吗......