题意

有一棵树，每个节点有一个权值。

任何两个不同的节点都会把他们权值的\(gcd\)告诉他们的\(LCA\)节点。问每个节点被告诉的最大的数。

题解

第一次接触到树的启发式合并。

用一个set维护每个节点权值的因子。

自下而上，把每一个节点和所有儿子分别合并，记录他们的最大的\(gcd\)（即两个集合合并时找到的最大的公共因子），并更新答案即可。

计算因子的时候，如果你对于每个权值都找一遍因子，那么时间复杂度是\(n\sqrt{n}\)的。所以可以提前预处理，是\(n\log(n)\)的。

代码

#include 
    
     #define FOPI freopen("in.txt", "r", stdin)#define FOPO freopen("out.txt", "w", stdout)using namespace std;typedef long long LL;const int maxn = 1e5 + 100;int n;set
     
       S[maxn];vector
      
        v[maxn], Y[maxn];int ans[maxn];int merge(int x, int y){    int res = 0;    if (S[x].size() < S[y].size())        swap(S[x], S[y]);    for (int it : S[y])    {        if (S[x].count(it))            res = max(res, it);        else            S[x].insert(it);    }    S[y].clear();    return res;}void dfs(int x){    for (int y : v[x])    {        dfs(y);        ans[x] = max(ans[x], merge(x, y));    }}void init(){    for (int i = 1; i <= 1e5; i++)        for (int j = i; j <= 1e5; j += i)            Y[j].push_back(i);}int main(){    memset(ans, -1, sizeof(ans));    init();    int x;    scanf("%d", &n);    for (int i = 2; i <= n; i++)        scanf("%d", &x), v[x].push_back(i);    for (int i = 1; i <= n; i++)    {        scanf("%d", &x);        for (int j : Y[x]) S[i].insert(j);    }    dfs(1);    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);}