吉林省长春市建设局网站,龙岩刚刚发生的事,广州联亨科技网站建设,手机微网站第二年续费吗Problem - G - Codeforces
题意#xff1a; 思路#xff1a;
首先#xff0c;目标值和结点权值是直接联系的#xff0c;最值不可能直接贪心#xff0c;一定是考虑去枚举一些东西#xff0c;依靠这种枚举可以遍历所有的有效情况#xff0c;思考的方向一定是枚举
如果去…Problem - G - Codeforces
题意 思路
首先目标值和结点权值是直接联系的最值不可能直接贪心一定是考虑去枚举一些东西依靠这种枚举可以遍历所有的有效情况思考的方向一定是枚举
如果去直接在链上枚举的话 复杂度是O(nq)肯定不行
注意到一条路径上的前缀或值不会超过 logV个因此考虑枚举前缀或值 关于每次跳使前缀或值变化的最深的点我是这样理解的
如果考虑在链上枚举如果前缀或值不变那么这样的枚举是无效的我们直接考虑跳着枚举只枚举所有有效情况
关于怎么跳其实可以参考树上倍增往上跳的跳法记录一个数组指向下一个结点在dfs上维护即可有点像在树链上DP
Code
#include bits/stdc.h#define int long longconstexpr int N 2e5 10;std::vectorint 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;
}
