（枚举 + 树上倍增）Codeforces Round 900 (Div. 3) G

亦凉 2024-02-26 07:04 27阅读 0赞

[Problem - G - Codeforces][]

题意：

![34732364ff234c308c2bde9cde9b9b34.png][]

思路：

首先，目标值和结点权值是直接联系的，最值不可能直接贪心，一定是考虑去枚举一些东西，依靠这种枚举可以遍历所有的有效情况，**思考的方向**一定是枚举

如果去直接在链上枚举的话， 复杂度是O(nq)，肯定不行

注意到一条路径上的前缀或值不会超过 logV个，因此考虑枚举前缀或值

![47c36ce4eb544f41bd90ca6b35b519fb.png][]

关于每次跳使前缀或值变化的最深的点，我是这样理解的

如果考虑在链上枚举，如果前缀或值不变，那么这样的枚举是无效的，我们直接考虑跳着枚举，只枚举所有**有效**情况

关于怎么跳其实可以参考树上倍增往上跳的跳法，记录一个数组指向下一个结点，在dfs上维护即可，有点像在树链上DP

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 2e5 + 10;
    
    std::vector<int> adj[N];
    
    int n;
    int a[N];
    int dep[N];
    int f[N][33], s[N][33], lst[N][33];
    
    void dfs(int u, int fa) {
        dep[u] = dep[fa] + 1;
        f[u][0] = fa;
        for (int j = 1; j <= 30; j ++) f[u][j] = f[f[u][j - 1]][j - 1];
        int val = a[u];
        for (int j = 30; j >= 0; j --) {
            if (!((val >> j) & 1)) {
                lst[u][j] = lst[fa][j];
                s[u][j] = s[fa][j];
            }else {
                lst[u][j] = u;
                s[u][j] = s[fa][j] + 1;
            }
        }
        for (auto v : adj[u]) {
            if (v == fa) continue;
            dfs(v, u);
        }
    }
    int lca(int u, int v) {
        if (dep[u] < dep[v]) std::swap(u, v);
        for (int j = 30; j >= 0; j --) {
            if (dep[f[u][j]] >= dep[v]) {
                u = f[u][j];
            }
        }
        if (u == v) return u;
        for (int j = 30; j >= 0; j --) {
            if (f[u][j] != f[v][j]) {
                u = f[u][j];
                v = f[v][j];
            }
        }
        return f[u][0];
    }
    int calc(int x, int y, int lca) {
        int res = 0;
        for (int j = 0; j <= 30; j ++) {
            if (s[x][j] + s[y][j] - s[lca][j] - s[f[lca][0]][j]) res ++;
        }
        return res;
    }
    void solve() {
        std::cin >> n;
        for (int i = 1; i <= n; i ++) {
            adj[i].clear();
            dep[i] = 0;
            for (int j = 30; j >= 0; j --) {
                f[i][j] = s[i][j] = lst[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i ++) std::cin >> a[i];
        for (int i = 1; i <= n - 1; i ++) {
            int u, v;
            std::cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(1, 0);
    
        int q;
        int ans = 0;
        std::cin >> q;
        while(q --) {
            int x, y;
            std::cin >> x >> y;
            int cur = x, val = a[x];
            ans = 0;
            while(1) {
                int nxt = 0, mx = 0;
                ans = std::max(ans, calc(x, cur, lca(x, cur)) + calc(cur, y, lca(cur, y)));
                for (int j = 30; j >= 0; j --) {
                    if (!((val >> j) & 1)) {
                        if (dep[lst[cur][j]] >= dep[lca(x, y)]) {
                            if (dep[lst[cur][j]] > mx) {
                                mx = dep[lst[cur][j]];
                                nxt = lst[cur][j];
                            }
                        }
                    }
                }
                if (!mx) break;
                val |= a[nxt];
                cur = nxt;
            }
            cur = y, val = a[y];
            while(1) {
                int nxt = 0, mx = 0;
                ans = std::max(ans, calc(x, cur, lca(x, cur)) + calc(cur, y, lca(cur, y)));
                for (int j = 30; j >= 0; j --) {
                    if (!((val >> j) & 1)) {
                        if (dep[lst[cur][j]] >= dep[lca(x, y)]) {
                            if (dep[lst[cur][j]] > mx) {
                                mx = dep[lst[cur][j]];
                                nxt = lst[cur][j];
                            }
                        }
                    }
                }
                if (!mx) break;
                val |= a[nxt];
                cur = nxt;
            }
            std::cout << ans << " ";
        }
        std::cout << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        std::cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/contest/1878/problem/G
[34732364ff234c308c2bde9cde9b9b34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/d9857c94c81142a8a2326d3e563aad91.png
[47c36ce4eb544f41bd90ca6b35b519fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/fc2a45963c48419a8a47f28a5acfef0f.png