题解：P16222 [ECUSTPC 2025] 荷塘月色

YZren · 2026-11-11 20:10:25 · 题解

荷塘月色

题意

ans= \frac{ \sum_{1\le x<y\le n} [\gcd(path(x,y))=\min(path(x,y))] \cdot\min(path(x,y)) }{ \binom n2 }

思路

注意到如果要贡献答案 k，需要满足两个条件。
1. 路径上的数都是 k 的倍数。
2. 路径上至少存在一个点权值等于 k。
考虑容斥掉第二个条件的限制，定义两个数组。
1. 令所有满足第一个条件的点对数为 dpf_k。
2. 令满足第一个条件但不满足第二个条件的点对数为 dpg_k。
那么答案就是 \binom n2 ^{-1}\sum_{i=1}^n i\times(dpf_i-dpg_i)。
如何快速计算两个数组，考虑直接枚举最小值，再枚举所有倍数，标记这些节点，如果标记的点之间有边连接，就用并查集合并，dpg_k 只是不把最小值标记即可。

::::success[Code]

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define f(i,j,k) for(int i=j;i<=k;i++)
#define F(i,j,k) for(int i=j;i>=k;i--)
namespace quick{
#define tp template<typename Type>
    namespace in{
        inline char getc(){
            static char buf[1<<23],*p1=buf,*p2=buf;
            return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
        }
        inline int read(char *s){
            *s=getc();
            while(isspace(*s)){*s=getc();if(*s==EOF) return 0;}
            while(!isspace(*s)&&*s!=EOF){s++;*s=getc();}
            *s='\0'; return 1;
        }
        tp inline int read(Type &x){
            x=0;bool k=false;char c=getc();
            while(!isdigit(c)){k|=(c=='-');c=getc();if(c==EOF) return 0;}
            while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getc();}
            x*=(k?-1:1); return 1;
        }
        template <typename Type,typename... Args>
        inline int read(Type &t,Args &...args){
            int res=0;
            res+=read(t);res+=read(args...);
            return res;
        }
    }
    using in::read;
    namespace out{
        char buf[1<<23];int p1=-1;const int p2=(1<<23)-1;
        inline void flush() {
            fwrite(buf,1,p1+1,stdout);
            p1=-1;
        }
        inline void putc(const char &c){
            if(p1==p2) flush();
            buf[++p1]=c;
        }
        inline void write(char *s){
            while(*s!='\0') putc(*s),s++;
        }
        tp inline void write(Type x){
            static char buf[30];int p=-1;
            if(x<0) {putc('-');x=-x;}
            if(x==0) putc('0');
            else for(;x;x/=10) buf[++p]=x%10+48;
            for(;p!=-1;p--) putc(buf[p]);
        }
        inline void write(char c) {putc(c);}
        template <typename Type,typename... Args>
        inline void write(Type t,Args ...args){
            write(t);write(args...);
        }
    }
    using out::write;
    using out::flush;
    tp inline Type max(const Type a,const Type b){
        if(a<b) return b;
        return a;
    }
    tp inline Type min(const Type a,const Type b){
        if(a<b) return a;
        return b;
    }
    tp inline Type abs(const Type a){
        return a>=0?a:-a;
    }
#undef tp
}
using namespace quick;
const int maxn=5e5+10,mod=998244353;
int T,n,u,v,a[maxn],fa[maxn],siz[maxn],dpf[maxn],dpg[maxn];
std::vector<int> vec[maxn],num[maxn];
inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod; y>>=1;
    }
    return res;
}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int merge(int x,int y){
    x=find(x); y=find(y);
    if(x==y) return 0;
    if(siz[x]>siz[y]) std::swap(x,y);
    int res=siz[x]*siz[y]%mod;
    fa[x]=y; siz[y]+=siz[x];
    return res;
}
inline void solve(){
    read(n); f(i,1,n) vec[i].clear(),num[i].clear();
    f(i,1,n-1) read(u,v),vec[u].emplace_back(v),vec[v].emplace_back(u);
    f(i,1,n) read(a[i]),num[a[i]].emplace_back(i);
    f(i,1,n){
        for(int j=i;j<=n;j+=i) for(auto y:num[j]) fa[y]=y,siz[y]=1;
        int res=0;
        for(int j=i;j<=n;j+=i) for(auto x:num[j]) for(auto y:vec[x]) if(a[y]%i==0) (res+=merge(x,y))%=mod;
        dpf[i]=res;
    }
    f(i,1,n){
        for(int j=i*2;j<=n;j+=i) for(auto y:num[j]) fa[y]=y,siz[y]=1;
        int res=0;
        for(int j=i*2;j<=n;j+=i) for(auto x:num[j]) for(auto y:vec[x]) if(a[y]%i==0&&a[y]!=i) (res+=merge(x,y))%=mod;
        dpg[i]=res;
    }
    int ans=0; f(i,1,n) (ans+=i*(dpf[i]-dpg[i]+mod)%mod)%=mod;
    write(ans*ksm((n*(n-1)/2)%mod,mod-2)%mod,'\n');
}
inline void work(){read(T); while(T--) solve();}
signed main(){work();flush();return !!!!!("YZren");}

::::