Gym 104025 M -Counting in Tree

https://codeforces.com/gym/104025/problem/M
prob.：
给一棵n个点树，定义一个节点的值为以这个节点为根的子树里，节点编号互质的对数，
nq 1e5
idea：
dsu on tree + 莫反
知道dsu和莫反之后大概就是个裸的题，从叶子开始，每次进来一个点x，计算这个x和子树有多少gcd==1的对数
预处理每个节点的值
∑ i = 1 n [ g c d ( a i , x ) = = 1 ] = ∑ i = 1 n ∑ d ∣ g c d ( a i , x ) μ ( d ) = ∑ i = 1 n ∑ d ∣ a i ∑ d ∣ x μ ( d )

​i=1∑n​[gcd(ai​,x)==1]=i=1∑n​d∣gcd(ai​,x)∑​μ(d)=i=1∑n​d∣ai​∑​d∣x∑​μ(d)​
这题不用分块，直接记录当前子树里所有数的 出现的(每个)因子的 和 （好拗口）
需要预处理一下每个数的因子，不然会喜提T26
套娃题但第一次写dsu现学莫反A了值得纪念一下，btw成电b站那个配合oiwiki学莫反真的很不错（！

code：
ps 代码后面附的样例答案是277，可以自测一下

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const ll N = 1e6 + 10;

vector<int> fac[N];
ll primes[N], p_tot = 0, mu[N];
bool st[N];

void sieve() {
    p_tot = 0;
    mu[1] = 1;
    for (ll i = 2; i < N; ++i) {
        if (!st[i]) primes[++p_tot] = i, mu[i] = -1;
        for (ll j = 1; primes[j] * i < N; ++j) {
            st[primes[j] * i] = 1;
            if (i % primes[j] == 0) {
                mu[i * primes[j]] = 0;
                break;
            }
            mu[i * primes[j]] = -mu[i];
        }
    }
}


vector<ll> g[N];

// sz: 子树大小
// big: 重儿子
// L[u]: 结点 u 的 DFS 序
// R[u]: 结点 u 子树中结点的 DFS 序的最大值
// Node[i]: DFS 序为 i 的结点
ll sz[N], big[N], L[N], R[N], Node[N], totdfn, ans[N];
ll cnt[N], tmpres;

void add(ll u) {
    for (auto i : fac[u]) {
        tmpres += cnt[i] * mu[i];
        cnt[i]++;
    }
}

void del(ll u) {
    for (auto i : fac[u]) {
        tmpres -= cnt[i] * mu[i];
        cnt[i]--;
    }
}

ll getAns() {
    return tmpres;
}

void dfs0(ll x, ll p) {
    L[x] = ++totdfn;
    Node[totdfn] = x;
    sz[x] = 1;
    for (ll to : g[x]) {
        if (to == p) continue;
        dfs0(to, x);
        sz[x] += sz[to];
        if (!big[x] || sz[big[x]] < sz[to]) big[x] = to;
    }
    R[x] = totdfn;
}

void dfs1(ll x, ll p, bool keep) {
    for (ll to : g[x]) {
        if (to != p && to != big[x]) dfs1(to, x, false);
    }

    if (big[x]) {
        dfs1(big[x], x, true);
    }

    for (ll to : g[x]) {
        if (to != p && to != big[x]) {
            for (ll i = L[to]; i <= R[to]; ++i) {
                add(Node[i]);
            }
        }
    }

    add(x);

    ans[x] = getAns();

    if (keep == false) {
        for (ll i = L[x]; i <= R[x]; ++i) {
            del(Node[i]);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    sieve();

    for (int i = 1; i <= (int) (1e5 + 10); ++i) {
        for (int j = 1; j <= i / j; ++j) {
            if (i % j == 0) {
                fac[i].push_back(j);
                if (i / j != j) fac[i].push_back(i / j);
            }
        }
    }

    ll n, q;
    cin >> n >> q;
    for (ll i = 1; i < n; ++i) {
        ll p;
        cin >> p;
        g[i + 1].push_back(p);
        g[p].push_back(i + 1);
    }

    dfs0(1, -1);

    dfs1(1, -1, false);

    while (q--) {
        ll x;
        cin >> x;
        cout << ans[x] << "\n";
    }

    return 0;
}

/*
30 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
1
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139