2367. Phi And MST

【题目描述】

给你一个完全图，有n个节点，标号为1..n  

每个点的权值就是自己的标号  

查询图中最小生成树有多少个，这个的最小生成树必须满足父亲节点的标号小于自己,边的权值是连接的两个点的标号的gcd  

有4个操作  

D u v 删除边(u,v)，保证有边相连。  

Q 查询最小生成树有多少个  

S 查询当前的最小生成树权值和为多少  

A 加一个节点，标号为当前最大的节点的标号+1，并且将他和每个节点连接一条边  

【输入格式】

第一行两个数n,m  

然后m行表示操作数  

【样例输入】

无

【样例输出】

无

【提示】

0% n<=10 m<=10 并且只有查询操作  

20% n<=1000 m<=1000 并且只有查询操作和加点操作  

60% n<=30000 m<=30000 保证图的连通性，并且每个节点被删除的边的个数不会超过sqrt(i)个,Q操作不超过20次  

100% n<=500000 m<=500000 保证图的连通性，并且每个节点i被删除的边的个数不会超过sqrt(i)个，最后一次操作是查询  

答案 mod 100000007  

删除的节点的标号必然>=1000  

【来源】

改编自某题