Codeforces 463E Caisa and Tree：DFS + 質因子分解

Codeforces 463E Caisa and Tree 題解

題目： 給一棵 n 節點樹，每節點有權值。兩類操作：

1. 查詢 1 u：在 u 到根的路徑上（不含 u），找權值與 val[u] 不互質（gcd > 1）且深度最大的節點。
2. 修改 2 u w：將節點 u 權值改為 w。修改操作 ≤ 50 次。

核心思路

• 修改次數極少（≤50），可每次修改後重新預處理所有節點答案，查詢 O(1) 回答。
• DFS 遍歷樹，維護每個質因子對應的「最深節點棧」。進入節點 u，將其所有質因子對應的棧頂記錄為 u 的候選答案（取最深），然後將 u 壓入各質因子棧；遞歸子樹；退出時彈出。
• 質因子分解預處理 10⁶ 內所有質數（共 78498 個），分解單個數 O(質因子數)。

詳細流程

1. 線性篩預計算 prime[] 陣列。
2. 初始讀入權值，對每個節點調用 fenjie(u, val[u]) 分解質因子存入 V[u]。
3. DFS(1, 0)：
   • ans[u] = -1，deep[u] = dep。
   • 遍歷 V[u] 中每個質因子 v：若 P[v] 非空，棧頂即為當前路徑上含此質因子的最深節點，更新 ans[u]；將 u 壓入 P[v]。
   • 遞歸子節點。
   • 回溯時將 u 從各質因子棧彈出。
4. 操作 1 直接輸出 ans[u]；操作 2 修改 val[u]，重新分解質因子，再次 DFS 預處理。

關鍵代碼

#include <cstdio>
#include <vector>
#include <map>
using namespace std;
#define N 100005
int prime[1229] = {2,3,5,...}; // 1000 以內質數
int n, q, ans[N], deep[N];
vector<int> G[N], V[N];
map<int, vector<int> > P; // 質因子 -> 節點棧

void dfs(int u, int f, int dep) {
    ans[u] = -1; deep[u] = dep;
    for (int i = V[u].size()-1; i >= 0; i--) {
        int v = V[u][i];
        if (P[v].empty()) { P[v].push_back(u); continue; }
        if (ans[u] == -1 || deep[ans[u]] < deep[P[v].back()])
            ans[u] = P[v].back();
        P[v].push_back(u);
    }
    for (int v : G[u]) if (v != f) dfs(v, u, dep+1);
    for (int v : V[u]) P[v].pop_back();
}

void fenjie(int u, int x) {
    V[u].clear();
    for (int j = 0; prime[j]*prime[j] <= x; j++)
        if (x % prime[j] == 0) {
            V[u].push_back(prime[j]);
            while (x % prime[j] == 0) x /= prime[j];
        }
    if (x != 1) V[u].push_back(x);
}

int main() {
    while (~scanf("%d%d", &n, &q)) {
        for (int i = 1; i <= n; i++) {
            int v; scanf("%d", &v);
            G[i].clear(); fenjie(i, v);
        }
        for (int i = 1; i < n; i++) {
            int u, v; scanf("%d%d", &u, &v);
            G[u].push_back(v); G[v].push_back(u);
        }
        dfs(1, -1, 0);
        while (q--) {
            int op, u; scanf("%d%d", &op, &u);
            if (op == 1) printf("%d\n", ans[u]);
            else {
                int w; scanf("%d", &w);
                fenjie(u, w);
                dfs(1, -1, 0);
            }
        }
    }
    return 0;
}

複雜度

預處理 O(n log val)；每次修改 O(n log val)；查詢 O(1)。總修改 ≤ 50，總時間約 50 × n log val，n=10⁵ 可在 3 秒內通過。

優化提示

• 用陣列模擬棧避免 map 開銷，質因子最大 10⁶，可開 vector P[1000001]。
• 質因子分解可預計算最小質因子 minp[x] 實現 O(log x) 分解。