题目描述

blablabla

样例

blablabla

算法1

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, s;
vector<int> a;
unordered_map<int, vector<int>> edges;

ll ans = 0;

class Segment_Tree {
private:
    struct node {
        int l, r;
        ll sum;
    };

    vector<node> tree;

    void build_tree(int l, int r, int root) {
        tree[root].l = l;
        tree[root].r = r;

        if (l == r) {
            tree[root].sum = 0;
            return;
        }

        int mid = (l + r) >> 1;
        if (l <= mid) build_tree(l, mid, root << 1);
        if (r > mid) build_tree(mid + 1, r, root << 1 | 1);
        tree[root].sum = (ll) (tree[root << 1].sum + tree[root << 1 | 1].sum);
    }

    void tree_update(int pos, int val, int root) {
        int l = tree[root].l;
        int r = tree[root].r;

        if (l == r) {
            tree[root].sum += val;
            return;
        }

        int mid = (l + r) >> 1;
        if (pos <= mid) {
            tree_update(pos, val, root << 1);
        } else {
            tree_update(pos, val, root << 1 | 1);
        }

        tree[root].sum = (ll) (tree[root << 1].sum + tree[root << 1 | 1].sum);
    }

    ll query_range(int L, int R, int root) {
        int l = tree[root].l;
        int r = tree[root].r;

        if (L <= l && R >= r) return tree[root].sum;

        ll sum = 0;
        int mid = (l + r) >> 1;
        if (L <= mid) sum += query_range(L, R, root << 1);
        if (R > mid) sum += query_range(L, R, root << 1 | 1);
        return sum;
    }

public:
    Segment_Tree(int n) {
        tree = vector<node>(n << 2);
    }

    void build(int n) {
        build_tree(1, n, 1);
    }

    void update(int pos, int val) {
        tree_update(pos, val, 1);
    }

    ll query(int L, int R) {
        return query_range(L, R, 1);
    }

};

Segment_Tree T(0);

vector<int> vis;

void dfs(int node, int parent) {
    int count = 0;
    for (int i = 2 * a[node]; i <= n; i += a[node]) {
        count += vis[i];
    }

    ans += T.query(a[node], n) - count;

    vis[a[node]] = 1;

    T.update(a[node], 1);

    for (auto next: edges[node]) {
        if (next == parent) continue;
        dfs(next, node);
    }

    T.update(a[node], -1);
    vis[a[node]] = 0;

}

int main() {
    cin >> n >> s;
    a = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

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

    vis = vector<int>(n + 1, 0);

    T = Segment_Tree(n);
    T.build(n);
    dfs(s, 0);

    cout << ans;
    return 0;
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla