分析

这不是 的模板题。先对于每个节点的值分解为所有因数。然后处理一个节点时，先处理轻儿子，取消其贡献。再处理重儿子保留贡献。最后暴力加上轻子树。因为一个点到根节点只有 条轻路径，所以子树也只会被暴力加 次。总的时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0' ;ch = getchar();}
    return f?-x:x;
}
const int N = 110000;
vector<int> h[N],G[N];
int n,L[N],R[N],id[N],Id,si[N],son[N];
int ans[N],cnt[N],C[N],Ans,Cnt;
void dfs(int x,int fa) {
    si[x] = 1;id[L[x] = ++Id] = x;
    for(auto y:G[x]) {
        if(y == fa) continue;
        dfs(y,x);si[x] += si[y];
        if(si[son[x]] < si[y]) son[x] = y; 
    }R[x] = Id;
}
void work(int x) {
    for(auto z:h[x]) {
        if(C[z]) {
            if(z > Ans) Ans = z,Cnt = C[z];
            else if(z == Ans) Cnt += C[z];
        }
    }
}
void calc(int x) {
    for(int i = L[x];i <= R[x];i++) work(id[i]);
}
void solve(int x,int fa,int keep) {
    for(auto y:G[x]) {
        if(y == son[x] || y == fa) continue;solve(y,x,0);
    } 
    if(son[x]) solve(son[x],x,1);
    Ans = 0;Cnt = 0;
    for(auto y:G[x]) {
        if(y == son[x] || y == fa) continue;
        calc(y);
        for(int i = L[y];i <= R[y];i++) {
            for(auto z:h[id[i]]) C[z]++;
        }
    }
    work(x);
    ans[x] = Ans;cnt[x] = Cnt;
    for(auto z:h[x]) C[z]++;
    if(keep) return;
    memset(C,0,sizeof(C));  
}
int main()
{
    n = read();
    for(int i = 1;i < n;i++) {
        int x = read(),y = read();
        G[x].push_back(y);G[y].push_back(x);
    }
    for(int i = 1;i <= n;i++) {
        int val = read();
        for(int j = 1;j * j <= val;j++) {
            if((val%j)) continue;
            h[i].push_back(j);
            if(j * j != val) h[i].push_back(val/j);
        }
    }
    dfs(1,0);
    solve(1,0,0);
    for(int i = 1;i <= n;i++) {
        printf("%d %d\n",ans[i],cnt[i]);
    }
    return 0;
}