# 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);
}
}
};
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;
}