Codeforces 1101D 点分治-蒲公英云

Codeforces 1101D 点分治

Myth丶恋晨 2021-12-12 02:07 345阅读 0赞

题意：有一颗树，每个点有一个点权，边权都是1，问路径上的所有点的gcd不是1的最长路径是多少？

思路：之前补这道题的时候，用分解质因数 + 树形DP做的，其实用点分治可以更暴力一点。对于这类统计树上路径的问题，点分治是一种通用，高效的解法。对于所有的路径，无非两种情况：经过某个点，不经过某个点，我们对于每个点统计的相当于是经过该点的路径的信息。点分治为以下几步：1：找重心。2：以找到的重心为根，解决经过该点的路径的问题。3：递归的找其它子树的重心，解决问题。找经过该点的路径时，直接搜索求gcd，所有说非常暴力无脑。找到之后暴力合并。复杂度应该是O(n * (log(n) ^ 2));

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
vector<int> G[maxn];
map<int, int> mp, tmp;
map<int, int>::iterator it1, it2;
bool v[maxn];
int sz[maxn], tot, mx, root, a[maxn], ans;
void add(int x, int y) {
    G[x].push_back(y);
    G[y].push_back(x);
}
void get_root(int x, int fa) {
    sz[x] = 1;
    int max_part = 0;
    for (auto y : G[x]) {
        if(y == fa || v[y]) continue;
        get_root(y, x);
        sz[x] += sz[y];
        max_part = max(max_part, sz[y]);
    }
    max_part = max(max_part, tot - sz[x]);
    if(max_part < mx) {
        mx = max_part;
        root = x;
    }
}
void get_ans(int x, int dep, int fa, int z) {
    if(z == 1) return;
    tmp[z] = max(tmp[z], dep);
    for (auto y : G[x]) {
        if(v[y] || y == fa) continue;
        get_ans(y, dep + 1, x, __gcd(z, a[y]));
    }
}
void solve(int x) {
    mp.clear();
    mp[a[x]] = 1;
    for (auto y : G[x]) {
        if(v[y]) continue;
        tmp.clear();
        get_ans(y, 1, x, __gcd(a[x], a[y]));
        for (it1 = mp.begin(); it1 != mp.end(); it1++) {
            for (it2 = tmp.begin(); it2 != tmp.end(); it2++) {
                if(__gcd(it1 -> first, it2 -> first) != 1) {
                    ans = max(ans, (it1 -> second) + (it2 -> second));
                }
            }
        }
        for (it2 = tmp.begin(); it2 != tmp.end(); it2++) {
            mp[it2 -> first] = max(mp[it2 -> first], (it2 -> second) + 1);
        }
    }
}
void div(int x) {
    v[x] = 1;
    solve(x);
    for (auto y : G[x]) {
        if(v[y]) continue;
        tot = sz[y];
        mx = 1e6;
        get_root(y, x);
        div(root);
    }
}
int main() {
    int n, x, y;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(a[i] > 1) ans = 1;
    }
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    tot = n;
    mx = 1e6;
    get_root(1, -1);
    div(root);
    printf("%d\n", ans);
}