MRO-Ant colony
根据下取整除法的性质 \((\left\lfloor\dfrac{\left\lfloor\dfrac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\dfrac{x}{yz}\right\rfloor)\)，我们可以反向考虑，即从特殊边开始，计算出从每个叶子到特殊边的路径上，要除以的那个分母是什么。
这个可以直接一遍dfs就出来了（可以把它当成 DP）。注意，当一段路径的分母已经爆 \(10^9\) 时就可以直接退出了，因为这样子不会有蚂蚁到得了特殊边。
然后，对于一个分母 \(d\)，所有 \(\in\Big[dk,d(k+1)\Big)\) 的蚁群数量都是合法的；故我们直接对蚁群数量排序然后二分再差分即可。
时间复杂度 \(O(n\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=1e9;
const int N=1e6+100;
int n,m,k,U,V,a[N];
LL d[N],res;
vector<int> v[N],u;
void dfs(int x,int fa,int lam){
if(v[x].size()==1){u.push_back(lam);return;}
if(1ll*lam*(v[x].size()-1)>INF) return;
lam*=(v[x].size()-1);
for(auto y:v[x]) if(y!=fa) dfs(y,x,lam);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
scanf("%d%d",&U,&V);
v[U].push_back(V);
v[V].push_back(U);
for(int i=1,x,y;i+1<n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(U,V,1);
dfs(V,U,1);
sort(a+1,a+m+1);
for(auto i:u){
LL l=1ll*k*i,r=1ll*(k+1)*i;
if(l>INF) continue;
d[lower_bound(a+1,a+m+1,l)-a]++;
d[lower_bound(a+1,a+m+1,r)-a]--;
}
for(int i=1;i<=m;i++)d[i]+=d[i-1],res+=d[i];
printf("%lld\n",res*k);
return 0;
}