题意：

给定一棵n个节点的树，并且根节点的编号为p，第i个节点有属性值vali, 定义F(i): 在以i为根的子树中，属性值是$val_i$的合约数的节点个数。y 是 x 的合约数是指 y 是合数且 y 是 x 的约数。小埃想知道$\sum_{i=1}^n i·F(i)$对1000000007取模后的结果.

思路：

有点类似之前做的一道CF题…就都是整体考虑。

一次DFS就可以了，从根开始，第一次碰到这个结点的时候F[i]减去当前这个$val_i$的合约数出现的次数。回溯的时候，F[i]加上当前这个$val_i$的合约数出现的次数，结果就是i的子树中是$val_i$的合约数的节点个数（子树包括自己）。所以要预处理出每个数字的合约数。

这里提一下这个复杂度的估计…我以前对DFS的复杂度估计有误解…

我以前一直以为DFS的复杂度肯定是2^n这样的，现在考虑一下本身这个树也就n个结点，所以这里的复杂度是O(n*sqrt(val))。

下次看到子树有几个符合要求的结点时可以考虑这种思路。

代码：

typedef long long ll;
bool vis[10010];
vector<int>hys[10010];//每个数的合约数
vector<int>g[20010];
ll val[20010];
ll cnt[10010];//当前i出现的次数
ll F[20010];
void init()
{
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=10000;i++)
    {
        if(!vis[i])
        {
            for(int j=2;i*j<=10000;j++)
                vis[i*j]=true;
        }
    }
    for(int i=2;i<=10000;i++)
    {
        if(vis[i])
        {
            for(int j=1;i*j<=10000;j++)
                hys[i*j].push_back(i);
        }
    }
}
void dfs(int id,int par)
{
    for(int i=0;i<hys[val[id]].size();i++)
        F[id]-=cnt[hys[val[id]][i]];
    cnt[val[id]]++;
    for(int i=0;i<g[id].size();i++)
    {
        if(g[id][i]!=par)
            dfs(g[id][i],id);
    }
    for(int i=0;i<hys[val[id]].size();i++)
        F[id]+=cnt[hys[val[id]][i]];
}
int main()
{
    int t,n,p,u,v;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
            scanf("%lld",&val[i]);
        memset(F,0,sizeof(F));
        memset(cnt,0,sizeof(cnt));
        dfs(p,-1);
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+i*F[i])%MOD;
        /*for(int i=1;i<=n;i++)
            printf("%lld ",F[i]);
        printf("\n");*/
        printf("%lld\n",ans);
    }
    return 0;
}