HDu6430 TeaTree 题解

维护一串线段树 + 线段树合并。

首先，注意到小于1e5的整数最多只有100多个因子。

那么我们先预处理小于1e5的所有整数的因子。

对于每个输入的权值，将他的所有因子插入到第i颗线段树上，线段树本身里面没有维护任何值，只是维护了左右儿子的存在性。

之后，我们从后往前扫描整个数组，因为从后面开始的由于输入格式一定是叶子结点，对于每个节点将以他为根的线段树合并到父亲节点上。

合并时，将当前父节点的答案更新为最大值。

合并的意义在于，以他为lca的节点的所有因子合并在一起，并找到最大相同因子。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

int n, ans[maxn], fa[maxn], a[maxn];

vector<int> fac[maxn];
int ls[maxn * 800] = {0}, rs[maxn * 800] = {0};
int root[maxn], tot = 0, f;

void update(int k, int l, int r, int& rt){
    if (!rt) rt = ++tot;
    if (l == r) return;
    int m = (l + r) >> 1;
    if (k <= m) update(k, l, m, ls[rt]);
    else update(k, m + 1, r, rs[rt]);
}
int join(int pre, int l, int r, int rt){
    if (!pre || !rt) return pre ^ rt;
    if (l == r) { ans[f] = max(ans[f], l); return rt;}
    int m = (l + r) >> 1;
    ls[rt] = join(ls[pre], l, m, ls[rt]);
    rs[rt] = join(rs[pre], m + 1, r, rs[rt]);
    return rt;
}

int main(){
    for (int i = 1; i < maxn; i++) for (int j = 1; i * j < maxn; j++)
        fac[i * j].push_back(i);
    scanf("%d", &n); ms(ans, -1);
    for (int i = 2; i <= n; i++) scanf("%d", &fa[i]);
    for (int x, i = 1; i <= n; i++) {
        scanf("%d", &x); root[i] = ++tot;
        for (int j = 0; j < fac[x].size(); j++) 
            update(fac[x][j], 1, maxn - 1, root[i]);
    }
    for (int i = n; i >= 1; i--){
        f = fa[i]; root[f] = join(root[i], 1, maxn - 1, root[f]);
    }
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}