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

Rnfmabj · 2025-07-19 00:08:43 · 题解

一个相对无脑的做法，树上启发式合并。早几个月过的时候题解区还没几篇题解，就想着后面有人补充就行，没想到现在还没有这个做法，于是简单写一下。

注意到题目的要求是一个对点统计子树内点对的形式，那么一个比化式子算贡献更直观的想法是开桶大力统计。具体地，对因数开桶，统计当前被计入过贡献的点里有多少个点是这个因数的倍数，然后后续暴力扫描当前点子树的时候，扫到的点是子树根的倍数即可直接让答案累加上子树根对应桶的计数器。

这样就是很裸的支持树上启发式合并的形式了，预处理所有点的因数集合后，正常增删贡献正常统计即可，时间复杂度和其他题解一样，是 O(nd(n)\log n) 的。常数也不大。

键盘直连大脑，码力代替思考。

//空中散歩の SOS 僕ファー　僕ファー　僕ファー ~
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef double db;
const ll maxn=1e5+5;
vector<ll>e[maxn];
ll a[maxn];
vector<ll>lst[maxn];
ll siz[maxn];
ll sn[maxn];
ll t[maxn];
void init(ll x,ll fa){
    siz[x]=1;
    for(auto v:e[x]){
        if(v==fa)continue;
        init(v,x);
        siz[x]+=siz[v];
        if(siz[v]>siz[sn[x]])sn[x]=v;
    }
}
void clr(ll x,ll fa){
    for(auto it:lst[a[x]]){
        t[it]=0;
    }
    for(auto v:e[x]){
        if(v==fa)continue;
        clr(v,x);
    }
}
ll ans=0;
void calc(ll x,ll fa,ll tar){
    if(a[x]%tar==0)ans+=t[tar]*2;
    for(auto v:e[x]){
        if(v==fa)continue;
        calc(v,x,tar);
    }
}
void ins(ll x,ll fa){
    for(auto it:lst[a[x]]){
        t[it]++;
    }
    for(auto v:e[x]){
        if(v==fa)continue;
        ins(v,x);
    }
}
void work(ll x,ll fa){
    for(auto v:e[x]){
        if(v==fa||v==sn[x])continue;
        work(v,x);
        clr(v,x);
    }
    if(sn[x])work(sn[x],x);
    for(auto v:e[x]){
        if(v==fa||v==sn[x])continue;
        calc(v,x,a[x]);
        ins(v,x);
    }
    ans+=2*t[a[x]];
    for(auto it:lst[a[x]]){
        t[it]++;
    }
    return ;
}
ll n;
void solve(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        if(!lst[a[i]].size()){
            for(ll j=1;j<=sqrt(a[i]);j++){
                if(a[i]%j)continue;
                lst[a[i]].push_back(j);
                if(a[i]/j!=j)lst[a[i]].push_back(a[i]/j);
            }
        }
    }
    for(ll i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    init(1,0);
    work(1,0);
    cout<<ans+n<<endl;
    return ;
}
ll T=1;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  cin>>T;
    for(ll kase=1;kase<=T;kase++){
        solve();
    }
    return 0;
}

注意了零处常数优化。