mssjtxwdSolution

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== mssjtxwd's Solution ==
''' 青云的计算方案(困难) '''

{{{
link:http://nanti.jisuanke.com/t/11135

1.假设所有点互质时的答案=A 则ans = A - gcd>=2的点对的距离和，这是第一步转化
2.转化后的问题类似gcd>=2的方案数，一个经典模型，从大到小枚举因子，再容斥计算
3.枚举因子为d，子问题变成拿出所有因子为d的点后，这些点相互之间的距离和
4.1 经典问题 树上一些点被染色，询问相互之间路径距离总和，点分治即可
4.2 学习一个 虚树 把这些关键点之间的无关点缩掉后即可DP来做
}}}

mssjtxwd's Solution

青云的计算方案(困难)

link:http://nanti.jisuanke.com/t/11135
1.假设所有点互质时的答案=A 则ans = A - gcd>=2的点对的距离和，这是第一步转化
2.转化后的问题类似gcd>=2的方案数，一个经典模型，从大到小枚举因子，再容斥计算
3.枚举因子为d，子问题变成拿出所有因子为d的点后，这些点相互之间的距离和
4.1 经典问题 树上一些点被染色，询问相互之间路径距离总和，点分治即可
4.2 学习一个 虚树 把这些关键点之间的无关点缩掉后即可DP来做