DDOSvoid's Blog

CF 986E Prince's Problem

发表于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

题目描述

https://codeforces.com/problemset/problem/986/E?f0a28=1

简要题意：给定一棵 $n$ 个点的无根树，每个点有一个点权 $a_i$，现在有 $m$ 次询问，每次询问给定一条树上的路径 $(u,v)$ 和权值 $w$，求 $\prod_{t\in (u,v)}gcd(a_t,w)$

$n\le 10^5,a_i,w\le 10^7$

Solution

我们考虑对于每个数分解质因数，对于每个质因数建虚树单独做，注意到 $a_i\le 10^7$，所以每个点最多只有不超过 $7$ 个不同的质因数，对于询问，也要按照质因数拆分，注意把询问的点也扔进虚树里

对于询问，我们将其拆成到根的树链，$dfs$ 的时候预处理即可，时间复杂度 $O(7n\log a_i)$

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
// LUOGU_RID: 94216105
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <stack>
#define maxn 100010
#define maxm 10000010
#define ll long long
using namespace std;

const int p = 1000000007;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
int pow_mod(int x, int n) {
    int s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s; 
}

bool isp[maxm]; int pri[maxm / 10], cnt, a[maxm], pid[maxm];
void init_isp(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, pid[i] = cnt, a[i] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1, a[i * pri[j]] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}

int n, m; 

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int id[maxn], dep[maxn], f[maxn][21];
void pre(int u, int fa) {
    static int cnt = 0;
    id[u] = ++cnt;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        f[v][0] = u; dep[v] = dep[u] + 1; pre(v, u); 
    }
}
void init_lca(int n) {
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
}
int get_lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; ~i; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; ~i; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

vector<int> G[maxn];
vector<tuple<int, int, int>> Q[maxn];
int w[maxn], ans[maxn], dis[maxn][24];
void dfs(int u, int fa, int e) {
    for (int i = 0; i <= 23; ++i) dis[u][i] = dis[fa][i];
    if (w[u]) for (int i = 0; i <= 23; ++i) dis[u][i] += min(i, w[u]);
    for (auto [k, opt, id] : Q[u]) {
        int t = pow_mod(e, dis[u][k]);
        if (opt > 0) ans[id] = mul(ans[id], t);
        else ans[id] = mul(ans[id], pow_mod(mul(t, t), p - 2));
    }
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u, e); 
    }
}
void clear(int u, int fa) {
    for (auto v : G[u]) {
        if (v == fa) continue;
        clear(v, u); 
    }
    w[u] = 0;
    for (int i = 0; i <= 23; ++i) dis[u][i] = 0;
    Q[u].clear(), G[u].clear();
}

vector<pair<int, int>> A[maxm  / 10];
vector<tuple<int, int, int, int>> B[maxm / 10];
inline bool cmp(const int &u, const int &v) { return id[u] < id[v]; } 
void solve(vector<pair<int, int>> &a, vector<tuple<int, int, int, int>> &b, int rt, int e) {
    vector<int> vec;
    for (auto [u, v] : a) w[u] += v, vec.push_back(u);
    for (auto [x, y, s, id] : b) {
        Q[x].emplace_back(s, 1, id);
        Q[y].emplace_back(s, 1, id);
        int lca = get_lca(x, y); 
        Q[lca].emplace_back(s, -1, id);
        ans[id] = mul(ans[id], pow_mod(e, min(w[lca], s)));
    }
    sort(vec.begin(), vec.end(), cmp), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    stack<int> S; S.push(rt);
    for (auto u : vec) {
        if (u == rt) continue; int lca = get_lca(u, S.top());
        while (S.top() != lca) {
            int t = S.top(); S.pop();
            if (id[S.top()] < id[lca]) S.push(lca);
            G[S.top()].push_back(t);
        } S.push(u);
    }
    while (S.top() != rt) {
        int t = S.top(); S.pop();
        G[S.top()].push_back(t);
    } dfs(rt, 0, e), clear(rt, 0); 
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; init_isp(10000000);
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y), add_edge(y, x); 
    }
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        while (x != 1) {
            int y = a[x], s = 0; 
            while (x % y == 0) ++s, x /= y;
            A[pid[y]].emplace_back(i, s);
        }
    } dep[1] = 1, pre(1, 0), init_lca(n);
    cin >> m;
    for (int i = 1; i <= m; ++i) ans[i] = 1; 
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        while (z != 1) {
            int t = a[z], s = 0;
            while (z % t == 0) ++s, z /= t;
            A[pid[t]].emplace_back(x, 0);
            A[pid[t]].emplace_back(y, 0);
            B[pid[t]].emplace_back(x, y, s, i); 
        } 
    }
    for (int i = 1; i <= cnt; ++i)
        if (B[i].size()) solve(A[i], B[i], 1, pri[i]);
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0;
}