我不知道题解应该叫什么名字

T7_Daniel · 2025-12-13 09:59:27 · 题解

先考虑这个问题的弱化版本：将 lca 换为祖先。

这个时候，我们发现这是一个很模板的树上线段树合并的经典运用。

所以我们可以将这个问题转化为：如何实现在合并的过程中处理 lca。

简单的方法是分情况讨论：

• 两个子树之间的贡献：在每一次合并，处理当前子树的信息和现在信息的贡献

即为：

ans+=ask(rt,1,n,a[x])*ask(srt,1,n,a[x]);//子树的匹配

• 自己和子树的贡献：全部处理完之后，再把有贡献的加上

即为：

ans+=ask(rt,1,n,a[x]);//自身的匹配

然后就可以码力连接大脑，数据结构代替思考了。

注意最后需要把答案乘 2 再加 n，因为点对是有序的，并且需要特判 x 和 y 相等的情况。

以下是代码，因为此题并不卡常，所以使用了 define int long long：

#include<bits/stdc++.h>
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define mid ((l+r)>>1)
using namespace std;

const int N=1e5+5,M=4e7+5;
struct node{int sum,ls,rs;}tr[M];
int a[N],ans,idx,n;vector<int> v[N];

inline int read(){
    int s=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s;
}

inline void add(int &p,int l,int r,int k){
    if(!p) p=++idx;
    if(l==r){tr[p].sum++;return;}
    if(k<=mid) add(ls(p),l,mid,k);
    else add(rs(p),mid+1,r,k);
}

inline int ask(int p,int l,int r,int x){
    if(!p) return 0;
    if(l==r) return tr[p].sum;
    if(x<=mid) return ask(ls(p),l,mid,x);
    else return ask(rs(p),mid+1,r,x);
}

inline void merge(int &x,int &y,int l,int r){
    if(!y) return;
    if(!x){x=y;return;}
    if(l==r){tr[x].sum+=tr[y].sum;return;}
    merge(tr[x].ls,tr[y].ls,l,mid);
    merge(tr[x].rs,tr[y].rs,mid+1,r);
}

inline int dfs(int x,int fa){
    int rt=0;//当前根节点 
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];
        if(y==fa) continue;
        int srt=dfs(y,x);
        ans+=ask(rt,1,n,a[x])*ask(srt,1,n,a[x]);//子树的匹配 
        merge(rt,srt,1,n);//合并 
    }
    ans+=ask(rt,1,n,a[x]);//自身的匹配 
    for(int i=1;i*i<=a[x];i++){
        if(a[x]%i==0){
            add(rt,1,n,i);
            if(i*i!=a[x]) add(rt,1,n,a[x]/i);
        }
    }
    return rt;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans*2+n;//因为点对是有序的，所以×2，然后加上自己和自己 
    return 0;
}