专栏文章

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

qqwl_doge
B4189题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minh8vfp
此快照首次捕获于
2025/12/02 02:23
3 个月前
此快照最后确认于
2025/12/02 02:23
3 个月前
查看原文

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

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

对于树上的一个非叶子节点 uu 与以它的子节点为根的子树因数有 a[u]a[u] 的节点数 v1,v2,v3...v_1,v_2,v_3... 其中 viv_i 表示 uu 的各个儿子的子树因数有 a[u]a[u] 的节点个数，那么以 uu 为 lca，这棵子树一共有这么多组合法的点对：v[1]+v[2]+v[3]+v[1]×v[2]+v[2]×v[3]+v[1]×v[3]...v[1]+v[2]+v[3]+v[1] \times v[2]+v[2] \times v[3]+v[1] \times v[3]... 也就是“个数相加，两两相乘”。
但这样计算还不够方便，化简一下，可以变为：v[1]×1+v[2]×(v[1]+1)+v[3]×(v[1]+v[2]+1)...v[1] \times 1+v[2] \times (v[1]+1)+v[3] \times (v[1]+v[2]+1)... 看出来规律了吧，怎么写应该都知道吧，我就不多讲了。
但是暴力枚举的时间在树为链的情况下可以达到 O(n2)\mathcal{O}(n^2) 的，考虑定义一个全局数组 dd，d[i]d[i] 表示截止目前，因数有 ii 的节点数的数量，那么我们就可以在 dfs 回来之后根据变化，推出子树因数有 ii 的节点数量，这样时间复杂度就变成了 O(nn)\mathcal{O}(n \sqrt n) 了，n≤105n \le 10^5 看来不会超。
对了，由于对于每一对点对 (i,j)(i,j) 也可以表示成点对 (j,i)(j,i)，并且每一对 (i,i)(i,i) 对答案也有贡献，所以不要忘记乘上二再加上 nn！

代码：

CPP
#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;
}
提交记录

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...