角色属性树

题意

给出一棵组织树和每个节点当前的属性值。

查询 1 x 要求回答：离 x 最近、并且和 x 有公共萌元素的上司是谁。这里“有公共萌元素”等价于两个属性值有公共质因子，也就是 $\gcd > 1$ 。

修改 2 x y 则把节点 x 的属性值改成 y。

思路

最直接的办法是每次查询都沿父链往上找第一个 $\gcd > 1$ 的祖先。

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> value(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> value[i];
    }

    vector<vector<int>> tree(n + 1);
    for (int i = 1; i <= n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    vector<int> parent(n + 1, 0);
    vector<int> order;
    order.push_back(1);
    for (int i = 0; i < (int)order.size(); ++i) {
        int u = order[i];
        for (int v : tree[u]) {
            if (v == parent[u]) {
                continue;
            }
            parent[v] = u;
            order.push_back(v);
        }
    }

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            int cur = parent[x];
            int ans = -1;

            // 直接沿父链向上找第一个 gcd 大于 1 的祖先。
            while (cur != 0) {
                if (std::gcd(value[cur], value[x]) > 1) {
                    ans = cur;
                    break;
                }
                cur = parent[cur];
            }
            cout << ans << '\n';
        } else {
            int x, y;
            cin >> x >> y;
            value[x] = y;
        }
    }
    return 0;
}

brute.cpp 每次查询都暴力爬父链，适合帮助理解和对拍。但如果树很深、查询很多，这样最坏会到 $O(nq)$ 。

真正的突破口在于：修改次数最多只有 50 次。

样例路径

这张图展示样例树，节点里同时写出编号和属性值：

graph TD
  A["1 / 10"] --> B["2 / 8"]
  B --> C["3 / 4"]
  C --> D["4 / 3"]

例如查询节点 3 时，它的属性值是 $4 = 2^2$ 。沿路径往上看，节点 $2$ 的属性值 $8 = 2^3$ 也含质因子 2，而且它比节点 1 更近，所以答案是 2。这说明题目的关键不在 gcd 本身，而在“当前路径上，哪个祖先最近含有某个公共质因子”。

所以可以把问题改写成：

先把每个点的属性值分解成不同质因子
DFS 整棵树时，对每个质因子维护一个“当前路径出现栈”
到达节点 u 时，枚举 u 的所有质因子
每个质因子的栈顶，都是一个候选最近祖先
在这些候选里选深度最大的那个，就是答案

由于修改次数很少，我们不必做复杂在线结构。每次修改后，重新分解该点质因子，再整树 DFS 重算一遍 answer[u] 即可。

代码

cpp

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170#include <bits/stdc++.h>
using namespace std;

const int MAXP = 46340;

struct Operation {
    int type;
    int x;
    int y;
};

struct Frame {
    int u;
    int parent;
    int state;
};

static vector<int> primes;
static unordered_map<int, int> prime_id;
static vector<vector<int>> prime_stacks;

int get_prime_id(int p) {
    auto it = prime_id.find(p);
    if (it != prime_id.end()) {
        return it->second;
    }
    int id = (int)prime_stacks.size();
    prime_id[p] = id;
    prime_stacks.push_back(vector<int>());
    return id;
}

vector<int> factorize_ids(int x) {
    vector<int> ids;
    int value = x;
    for (int p : primes) {
        if (1LL * p * p > value) {
            break;
        }
        if (value % p == 0) {
            ids.push_back(get_prime_id(p));
            while (value % p == 0) {
                value /= p;
            }
        }
    }
    if (value > 1) {
        ids.push_back(get_prime_id(value));
    }
    return ids;
}

void build_primes() {
    vector<int> is_prime(MAXP + 1, 1);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= MAXP; ++i) {
        if (!is_prime[i]) {
            continue;
        }
        primes.push_back(i);
        if (1LL * i * i <= MAXP) {
            for (int j = i * i; j <= MAXP; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}

void recompute_answers(const vector<vector<int>> &tree,
                       const vector<vector<int>> &factor_ids,
                       vector<int> &answer,
                       vector<int> &depth) {
    int n = (int)tree.size() - 1;
    vector<Frame> st;
    st.reserve(n * 2);
    st.push_back({1, 0, 0});
    depth[1] = 0;

    while (!st.empty()) {
        Frame cur = st.back();
        st.pop_back();

        int u = cur.u;
        int parent = cur.parent;

        if (cur.state == 0) {
            int best = -1;
            int best_depth = -1;

            // 枚举当前点的所有不同质因子，看看路径上最近的同类祖先是谁。
            for (int pid : factor_ids[u]) {
                if (!prime_stacks[pid].empty()) {
                    int candidate = prime_stacks[pid].back();
                    if (depth[candidate] > best_depth) {
                        best_depth = depth[candidate];
                        best = candidate;
                    }
                }
            }
            answer[u] = best;

            for (int pid : factor_ids[u]) {
                prime_stacks[pid].push_back(u);
            }

            st.push_back({u, parent, 1});
            for (int i = (int)tree[u].size() - 1; i >= 0; --i) {
                int v = tree[u][i];
                if (v == parent) {
                    continue;
                }
                depth[v] = depth[u] + 1;
                st.push_back({v, u, 0});
            }
        } else {
            for (int pid : factor_ids[u]) {
                prime_stacks[pid].pop_back();
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build_primes();

    int n, q;
    cin >> n >> q;

    vector<int> value(n + 1);
    vector<vector<int>> factor_ids(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> value[i];
    }

    vector<vector<int>> tree(n + 1);
    for (int i = 1; i <= n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i) {
        factor_ids[i] = factorize_ids(value[i]);
    }

    vector<int> answer(n + 1, -1);
    vector<int> depth(n + 1, 0);
    recompute_answers(tree, factor_ids, answer, depth);

    for (int i = 1; i <= q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            cout << answer[x] << '\n';
        } else {
            int x, y;
            cin >> x >> y;
            value[x] = y;
            factor_ids[x] = factorize_ids(value[x]);
            recompute_answers(tree, factor_ids, answer, depth);
        }
    }
    return 0;
}

复杂度

每次整树重算都只需 DFS 一遍，并枚举每个点有限个不同质因子，所以单次可视为 $O(n)$ 。修改次数最多 $50$ ，因此总复杂度约为 $O((c+1) \cdot n + q)$ ，空间复杂度是 $O(n)$ 。

总结

这题的关键是抓住“更新少、查询多”这个结构特征。与其为每次查询单独向上找，不如每次修改后把整棵树的答案一次性重算出来。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

样例路径

代码

复杂度

总结

一图流解析