题目链接
来源：HDU 2025暑期多校第一场 G
HDU 链接（没有参加好像打不开）
BUCTOJ 链接（上面打不开就去这里）
题目描述
给定一棵大小为 \(n\) 的树，每个节点有点权。请求出有多少条简单路径（长度可以为 0），使得路径所包括的所有点（包括路径两端的点）点权的最小公倍数是 \(x\)。
两条简单路径不同，当且仅当树上至少存在一条边，它在其中一个路径里而不在另一个路径里。
说明/提示
对于所有的数据，\(1 \le n \le 10^5\)，\(\sum n \le 3 \times 10^5\)，\(1 \le x,a_i \le 10^7\)。
| 子任务 | 特殊限制 | 分值 |
|---|---|---|
| \(1\) | \(n,x,a_i \le 10\) | \(20\) |
| \(2\) | \(n \le 500\) | \(20\) |
| \(3\) | \(x\) 是质数 | \(20\) |
| \(4\) | \(v=u+1\) | \(20\) |
| \(5\) | 无 | \(20\) |
解题思路
官方题解的方法是神秘的高维前缀和 DP，还有使用莫比乌斯反演的，也很好理解，这篇题解给出与莫比乌斯反演类似的容斥方法，不会莫比乌斯反演的也能看懂。
考虑题目要求的是 \(\operatorname{lcm}\) 恰好等于 \(x\) 的路径条数，那我们弱化一下条件：求 \(\operatorname{lcm}\) 为 \(x\) 约数的路径条数。
因此，我们定义以下状态：
- \(f_i\)：\(\operatorname{lcm}\) 等于 \(i\) 的路径条数。
- \(g_i\)：\(\operatorname{lcm}\) 为 \(i\) 约数的路径条数。
那么容斥一下，\(f_i=g_i-\sum_{d\mid i\land d\neq i}f_d\)。因此，只要算出 \(x\) 所有约数的 \(g\) 值，就可以算出 \(f_x\) 的值了。
考虑 \(g_i\) 的计算方式。路径的 \(\operatorname{lcm}\) 为 \(i\) 的约数，当且仅当路径上每个点的点权为 \(i\) 的约数。因此，把点权不是 \(i\) 的约数的点删去后，剩下的所有路径均满足要求。对于大小为 \(s\) 的联通块，其中的路径条数为 \(\frac{s(s-1)}{2}\) 条。这样，我们就可以在 \(O(n)\) 的复杂度内计算出 \(g_i\) 的值。
由于 \(x\leq 10^7\)，\(10^7\) 内任意数的因数个数不超过 \(448\)，最终的时间复杂度为 \(O(448^2n)\)，且严重不满 （尽管这样但也跑得很慢） ，可以过的。
参考代码
//代码来自 id:AC___
#include <bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;int t,n,x,cnt,ans;
int a[N],b[N],f[10000005];
vector<int> e[N],v;void dfs(int x,int fa) {b[x]=0,cnt++;for(int i:e[x]) if(i!=fa && b[i]) dfs(i,x);
}int sol(int o) {for(int i=1; i<=n; i++) b[i]=!(o%a[i]);int sum=0;for(int i=1; i<=n; i++)if(b[i]) {cnt=0;dfs(i,0);sum+=cnt*(cnt+1)/2;}return sum;
}main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;while(t--) {memset(f,0,sizeof f);cin>>n>>x;v.clear();for(int i=1; i<=n; i++) e[i].clear();for(int i=1,u,v; i<n; i++) {cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i*i<=x; i++)if(x%i==0) {v.push_back(i);if(i*i!=x) v.push_back(x/i);}sort(v.begin(),v.end());for(int i:v) {f[i]=sol(i);for(int j:v) {if(i==j) break;if(i%j==0) f[i]-=f[j];}}cout<<f[x]<<'\n';}
}