Codeforces 1101D 点分治

Myth丶恋晨 2021-12-12 02:07 239阅读 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);
    }

转载于:https://www.cnblogs.com/pkgunboat/p/11158772.html