题解：B4189 [中山市赛 2024] 树上开花

qwl_doge · 2025-10-27 22:16:38 · 题解

题解：B4189 [中山市赛 2024] 树上开花

upd：2025-11-08，改正了一些错误的小细节。

对于树上的一个非叶子节点 u 与以它的子节点为根的子树因数有 a[u] 的节点数 v_1,v_2,v_3... 其中 v_i 表示 u 的各个儿子的子树因数有 a[u] 的节点个数，那么以 u 为 lca，这棵子树一共有这么多组合法的点对：v[1]+v[2]+v[3]+v[1] \times v[2]+v[2] \times v[3]+v[1] \times v[3]... 也就是“个数相加，两两相乘”。

但这样计算还不够方便，化简一下，可以变为：v[1] \times 1+v[2] \times (v[1]+1)+v[3] \times (v[1]+v[2]+1)... 看出来规律了吧，怎么写应该都知道吧，我就不多讲了。

但是暴力枚举的时间在树为链的情况下可以达到 \mathcal{O}(n^2) 的，考虑定义一个全局数组 d，d[i] 表示截止目前，因数有 i 的节点数的数量，那么我们就可以在 dfs 回来之后根据变化，推出子树因数有 i 的节点数量，这样时间复杂度就变成了 \mathcal{O}(n \sqrt n) 了，n \le 10^5 看来不会超。

对了，由于对于每一对点对 (i,j) 也可以表示成点对 (j,i)，并且每一对 (i,i) 对答案也有贡献，所以不要忘记乘上二再加上 n！

代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=100005;
int n,a[N],x,y,ans;
vector<int> g[N];
int d[N];
void yin(int x){
    for(int i=1;i*i<=x;i++){
        if(x%i==0){
            d[i]++;
            if(i!=x/i){
                d[x/i]++;
            }
        }
    }
}
void dfs(int u,int fa){
    int sum=0;
    yin(a[u]);
    sum=1;
    for(int v:g[u]){
        if(v==fa)continue;
        int yuan=d[a[u]];
        dfs(v,u);
        int geng=d[a[u]]-yuan;
//      cout<<"u:"<<u<<" sum:"<<sum<<" geng:"<<geng<<endl;
        ans+=(sum*geng);
//      cout<<"ans:"<<ans<<endl;
        sum+=geng;
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans*2+n;
}

提交记录