当前位置: 首页 > news >正文

黄金替罪羊

题面

黄金替罪羊实在是太难玩了,所以开拓者弄了个简化版。

黄金替罪羊需要替罪羊和开拓者的配合一起完成任务。

地图可以认为是一棵带权树,每次开拓者会问你一个有序点对 (u,v),表示起点为 u 而终点为 v,在开拓者的指令下会出现替罪羊,替罪羊会出现在 u,对于替罪羊和开拓者的配合程度,开拓者给出定义,是当替罪羊出现的时候开拓者的位置到替罪羊的位置之间经过的所有边的异或和。

开拓者想知道对于所有的发出指令的位置,替罪羊和开拓者的配合程度达到的最大值。开拓者不会走除了 (u,v) 的简单路径之外的点,所以她也只能在 (u,v) 之间的简单路径上发出指令。

思路

首先考虑暴力,我们发现可以暴力处理路径,然后暴力求答案,这样子是计算后求 max。

我们考虑对max进行优化,可以建立01字典树然后优化max的过程

继续优化,我们可以将u到v转化成u到lca和v到lca,所以我们可以维护从根到x的01字典树进行维护,具体来讲,我们记录可以产生贡献的深度最大的点,如果这个深度比lca大,说明可以产生贡献。

继续优化,可以离线下来,动态维护dfs栈

考虑退栈的时候会存在问题,因为max没有逆运算,我们可以标记上一个max的值,回溯时变成上一个max的值即可,这里利用栈的特性

代码

#include <iostream>
#include <vector>using namespace std;const int MaxN = 1e5 + 10, MaxM = 28 * MaxN, MaxK = 18;struct S {int v, w, id;
};struct Node {int nxt[2], mx;Node() {nxt[0] = nxt[1] = mx = -1;}
} trie[MaxM];int f[MaxN][MaxK], rt[MaxN], d[MaxN], dep[MaxN], tot, t, n, q, m, top;
vector<S> g[MaxN], qu[MaxN];void insert(int now, int lst, int x, int w, int p = 0) {rt[now] = ++m, trie[m] = trie[rt[lst]], p = m;for (int i = 30 - 1; i >= 0; i--) {bool c = x & (1 << i);if (trie[p].nxt[c] == -1) trie[p].nxt[c] = ++m;else trie[++m] = trie[trie[p].nxt[c]], trie[p].nxt[c] = m;p = trie[p].nxt[c];trie[p].mx = w;}
}int query(int u, int w, int x, int p = 0, int res = 0) {p = rt[u];for (int i = 30 - 1; i >= 0; i--) {bool c = w & (1 << i);if (~trie[p].nxt[!c] && trie[trie[p].nxt[!c]].mx >= x) p = trie[p].nxt[!c], res ^= (1 << i);else p = trie[p].nxt[c];}return res;
}void DFS(int x, int fa = 0) {f[x][0] = max(1, fa);for (int i = 1; i < MaxK; i++) {f[x][i] = f[f[x][i - 1]][i - 1];}insert(x, fa, d[x], dep[x]);for (auto i : g[x]) {if (i.v == fa) continue;d[i.v] = d[x] ^ i.w, dep[i.v] = dep[x] + 1, DFS(i.v, x); }
}int GO(int x, int k) {for (int i = MaxK - 1; i >= 0; i--) {if (k & (1 << i)) x = f[x][i];}return x;
}int LCA(int x, int y) {if (dep[x] < dep[y]) swap(x, y);x = GO(x, dep[x] - dep[y]);if (x == y) return x;for (int i = MaxK - 1; i >= 0; i--) {if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];}return f[x][0];
}int main() {ios::sync_with_stdio(0), cin.tie(0);for (cin >> t; t; t--) {cin >> n >> q, tot = m = 0;for (int i = 1; i <= n; i++) vector<S>().swap(g[i]);for (int i = 1, u, v, w; i < n; i++) {cin >> u >> v >> w;g[u].push_back({v, w, i}), g[v].push_back({u, w, i});}DFS(1);for (int i = 1, u, v, lca; i <= q; i++) {cin >> u >> v, lca = LCA(u, v);cout << max(query(u, d[u], dep[lca]), query(v, d[u], dep[lca])) << '\n';}for (int i = 1; i <= m; i++) trie[i] = Node();}return 0;
}
http://www.hskmm.com/?act=detail&tid=24475

相关文章:

  • P5301 [GXOI/GZOI2019] 宝牌一大堆
  • 10.4 2025多校冲刺CSP模拟赛2 改题记录
  • 【比赛记录】2025CSP-S模拟赛58
  • 回忆有感
  • 框架高效的系统的演进如何塑造人工智能的深层语义分析能力
  • 『回忆录』高二上第一次月考——压力下的崛起,意料外的突破
  • AutoCAD 2025安装包下载 CAD免费下载 永久免费激活 附详细安装教程
  • 微分和积分的区别
  • 202509_QQ_secret
  • 4 对拍杂谈
  • Matlab R2024b下载及详细安装教程,附永久免费Matlab安装包
  • Luogu P1966
  • 题解:P14036 [PAIO 2025] Rooks
  • 2025/8/26
  • 27 考研初试时间大约是什么时候?
  • 数据结构 - 跳表 Skip List
  • 06. 定时器
  • NOIP之前的复健记录
  • Linux 命令行安装达梦数据库
  • Google开源Tunix:JAX生态的LLM微调方案来了
  • 实用指南:Matlab通过GUI实现点云的快速全局配准(FGR)
  • 『OI 回忆录』停课有感
  • 『回忆录』初三第三学月
  • 完整教程:MySQL 5.7 主主复制 + Keepalived 高可用配置实例
  • 题解:P14074 [GESP202509 五级] 有趣的数字和
  • 解码Huffman 编码与 Huffman 树
  • 『回忆录』初三来高中的半学期
  • 10.1 容器云部署准备(一) - 实践
  • 关于缓冲区以及输出方式
  • 漏洞赏金计划的困境:i915漏洞与ChromeOS、Intel赏金项目剖析