Codeforces 1878G enumeration + tree multiplication

Question meaning

Portal Codeforces 1878G wxhtzdy ORO Tree

Solution

The answer depends on all points along the queried path. Bitwise AND is monotonic and can only enumerate the bits on each digit on the path.

1

1

1 The first occurrence of the position, the scale of this position is

O

(

log

?

max

?

{

a

}

)

O(\log\max\{a\})

O(logmax{a}). Top-down maintenance of each digital

1

1

1 The node with the largest depth appears. At this time, the node with the largest depth can be processed.

u

l

c

a

(

u

,

v

)

u\rightarrow lca(u,v)

The position on u→lca(u,v) that needs to be enumerated. Consider the maximal nature of the answer, easily observable, only enumerate

u

,

v

u,v

u, v and

u

l

c

a

(

u

,

v

)

,

v

l

c

a

(

u

,

v

)

u\rightarrow lca(u,v),v\rightarrow lca(u,v)

The corresponding positions of u→lca(u,v),v→lca(u,v) are enough.

Preprocess the multiplied information on the tree and update the answer by enumerating the intermediate positions. total time complexity

O

(

n

log

?

n

log

?

max

?

{

a

}

)

O(n\log n\log\max\{a\})

O(nlognlogmax{a}).

#include <bits/stdc + + .h>
using namespace std;
constexpr int LG_N = 18, LG_A = 30;
int main() {<!-- -->
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt;
    cin >> tt;
    while (tt--) {<!-- -->
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; + + i) {<!-- -->
            cin >> a[i];
        }
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; + + i) {<!-- -->
            int u, v;
            cin >> u >> v;
            u -= 1, v -= 1;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<vector<int>> par(n, vector<int>(LG_N, -1)), f(n, vector<int>(LG_N));
        vector<int> dep(n);
        function<void(int, int, int)> dfs = [ & amp;](int v, int p, int d) {<!-- -->
            dep[v] = d;
            par[v][0] = p;
            f[v][0] = a[v];
            for (int i = 0; i + 1 < LG_N; + + i) {<!-- -->
                if ((2 << i) <= d + 1) {<!-- -->
                    par[v][i + 1] = par[par[v][i]][i];
                    f[v][i + 1] = f[v][i] | f[par[v][i]][i];
                }
            }
            for (int u : g[v]) {<!-- -->
                if (u != p) {<!-- -->
                    dfs(u, v, d + 1);
                }
            }
        };
        dfs(0, -1, 0);
        auto lca = [ & amp;](int u, int v) {<!-- -->
            if (dep[v] < dep[u]) {<!-- -->
                swap(v, u);
            }
            for (int i = 0; i < LG_N; + + i) {<!-- -->
                if ((dep[v] - dep[u]) >> i & amp; 1) {<!-- -->
                    v = par[v][i];
                }
            }
            if (u == v) {<!-- -->
                return v;
            }
            for (int i = LG_N - 1; i >= 0; --i) {<!-- -->
                if (par[v][i] != par[u][i]) {<!-- -->
                    v = par[v][i];
                    u = par[u][i];
                }
            }
            return par[v][0];
        };
        vector<vector<int>> pos(n, vector<int>(LG_A));
        {<!-- -->
            function<void(int, vector<int>)> get = [ & amp;](int v, vector<int> tmp) {<!-- -->
                for (int i = 0; i < LG_A; + + i) {<!-- -->
                    if (a[v] >> i & amp; 1) {<!-- -->
                        tmp[i] = v;
                    }
                }
                pos[v] = tmp;
                for (int u : g[v]) {<!-- -->
                    if (u != par[v][0]) {<!-- -->
                        get(u, tmp);
                    }
                }
            };
            vector<int> tmp(LG_A, -1);
            get(0, tmp);
        }
        int q;
        cin >> q;
        while (q--) {<!-- -->
            int u, v;
            cin >> u >> v;
            u -= 1, v -= 1;
            vector<int> tmp{<!-- -->u, v};
            int p = lca(u, v);
            auto add = [ & amp;](int v, int p) {<!-- -->
                for (int i = 0; i < LG_A; + + i) {<!-- -->
                    int u = pos[v][i];
                    if (u != -1 & amp; & amp; dep[u] >= dep[p]) {<!-- -->
                        tmp.push_back(u);
                    }
                }
            };
            add(u, p);
            add(v, p);
            auto get = [ & amp;](int u, int v) {<!-- -->
                auto get_or = [ & amp;](int v, int p) {<!-- -->
                    int s = 0;
                    for (int i = LG_N - 1; i >= 0; --i) {<!-- -->
                        int u = par[v][i];
                        if (u != -1 & amp; & amp; dep[u] >= dep[p]) {<!-- -->
                            s |= f[v][i];
                            v = par[v][i];
                        }
                    }
                    s |= f[p][0];
                    return s;
                };
                int p = lca(u, v);
                int x = get_or(u, p) | get_or(v, p);
                return __builtin_popcount(x);
            };
            int res = 0;
            for (int w : tmp) {<!-- -->
                res = max(res, get(u, w) + get(w, v));
            }
            cout << res << ' ';
        }
        cout << '\
';
    }

    return 0;
}