[VMware校园挑战赛-牛客挑战赛40 E] 小V和gcd树

• 小V和gcd树

题目描述

给定一棵树，树带点权，树的边权等于边两端点权的 。

有两种操作 ：

1. 更改一个点的点权，同时与之相连的边权也跟着改变。

2. 询问两个点的链上边权小于等于 的个数。

正解

先将一下复杂度吧 ，挺暴力的。

考虑根号分治。

修改 ：

对于一个度数大于 的点，修改时只修改点权，忽视其边权的贡献（查询时再暴力求 计算贡献） 。

对于一个度数小于 的点，暴力修改其连出去的边权。

修改时复杂度瓶颈在度数小于 的点，时间复杂度为 。

查询 :

查询的时候暴力跳 统计答案，然后对于度数大于 的点，还要求 。

但是度数大于 的点不会超过 个，查询总复杂度为 。

代码

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e8;
const int N = 20005;
const int B = 150;

int n, q;
int deg[N], dep[N];
int a[N], fa[N], fe[N];

vector<int> g[N];

inline int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

void preDfs(int u) {
    dep[u] = dep[fa[u]] + 1;
    for(int v : g[u]) {
        if(v == fa[u]) continue;
        fa[v] = u, fe[v] = (deg[u] > B || deg[v] > B ? inf : gcd(a[u], a[v]));
        preDfs(v);
    }
}

int main() {
    n = read(), q = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1, u, v; i < n; ++i) {
        u = read(), v = read();
        ++deg[u], ++deg[v];
        g[u].push_back(v), ++deg[u];
        g[v].push_back(u), ++deg[v];
    }

    preDfs(1);
    for(int i = 1, opt, u, v, x; i <= q; ++i) {
        opt = read(), u = read(), v = read();
        if(opt == 1) {
            a[u] = v;
            if(deg[u] > B) continue;
            for(int v : g[u]) {
                if(deg[v] > B) continue;
                if(fa[u] == v) {
                    fe[u] = gcd(a[u], a[v]);
                } else {
                    fe[v] = gcd(a[u], a[v]);
                }
            }
        } else {
            x = read();
            int ans = 0;
            if(dep[u] < dep[v]) swap(u, v);
            while(dep[u] > dep[v]) {
                ans += (fe[u] <= x);
                if(deg[u] > B || deg[fa[u]] > B)
                    ans += (gcd(a[u], a[fa[u]]) <= x);
                u = fa[u];
            }
            if(u == v) goto print;
            while(u != v) {
                ans += (fe[u] <= x);
                if(deg[u] > B || deg[fa[u]] > B)
                    ans += (gcd(a[u], a[fa[u]]) <= x);
                u = fa[u];
                ans += (fe[v] <= x);
                if(deg[v] > B || deg[fa[v]] > B)
                    ans += (gcd(a[v], a[fa[v]]) <= x);
                v = fa[v];
            }
            print :
            printf("%d\n", ans);
        }
    }
    return 0;
}