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

Problem - G - Codeforces

题意：

思路：

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

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

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

 

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

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

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

Code：

#include <bits/stdc++.h>#define int long longconstexpr 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;
}