HDU 4757 Tree(可持久化字典树)(2013 ACM/ICPC Asia Regional Nanjing Online)
2024-09-27 16:11:48
Problem Description
Zero and One are good friends who always have fun with each other. This time, they decide to do something on a tree which is a kind of graph that there is only one path from node to node. First, Zero will give One an tree and every node in this tree has a value. Then, Zero will ask One a series of queries. Each query contains three parameters: x, y, z which mean that he want to know the maximum value produced by z xor each value on the path from node x to node y (include node x, node y). Unfortunately, One has no idea in this question. So he need you to solve it.
Input
There are several test cases and the cases end with EOF. For each case:
The first line contains two integers n(1<=n<=10^5) and m(1<=m<=10^5), which are the amount of tree’s nodes and queries, respectively.
The second line contains n integers a[1..n] and a[i](0<=a[i]<2^{16}) is the value on the ith node.
The next n–1 lines contains two integers u v, which means there is an connection between u and v.
The next m lines contains three integers x y z, which are the parameters of Zero’s query.
Output
For each query, output the answer.
题目大意:给你一颗n个点的树,每个点有一个权值。然后有m个询问,问从x到y的简单路径中,权值 xor z最大是多少。
思路:可持久化的0-1字典树,每个点在父节点的历史版本上新建一棵字典树,字典树上的每个结点给一个值记录从这个结点到树的根节点,有多少个权值会经过这个字典树上的结点。询问的时候在字典树上奏即可。由于a[i]<2^16,那么字典树的深度最大为16,空间复杂度为O(16 * n)。
PS:tarjan果然要比RMQ快啊。
PS2:数据保障z<2^16,虽然题目没讲……
代码(1265MS):
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std; const int MAX = ;
const int MAXN = * MAX;
const int MAXE = * MAXN; int head[MAXN], weight[MAXN], fa[MAX];
bool vis[MAX];
int to[MAXE], next[MAXE], id[MAXE];
int n, m, ecnt; inline void init() {
memset(head, , sizeof(head));
memset(vis, , sizeof(vis));
for(int i = ; i <= n; ++i) fa[i] = i;
ecnt = ;
} inline void add_edge(int u, int v, int i) {
to[ecnt] = v; id[ecnt] = i; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; id[ecnt] = i; next[ecnt] = head[v]; head[v] = ecnt++;
} struct QUERY {
int x, y, lca, z;
void read(int i) {
scanf("%d%d%d", &x, &y, &z);
add_edge(x + n, y + n, i);
}
} Query[MAX]; int get_set(int x) {
return fa[x] == x ? x : fa[x] = get_set(fa[x]);
} void dfs_LCA(int u, int f) {
for(int p = head[u]; p; p = next[p]) {
int &v = to[p];
if(v == f) continue;
dfs_LCA(v, u);
fa[v] = u;
}
vis[u] = true;
for(int p = head[u + n]; p; p = next[p]) {
int v = to[p] - n;
if(vis[v]) Query[id[p]].lca = get_set(v);
}
} struct Node {
int go[], cnt;
} tree[ * MAX];
int root[MAX], Tcnt; void init_tree() {
Tcnt = ; root[] = ;
} int insert(int x, int val) {
tree[Tcnt] = tree[x];
int ret = x = Tcnt++;
for(int i = ; i >= ; --i) {
int idx = (val >> i) & , t = Tcnt++;
tree[t] = tree[tree[x].go[idx]];
++tree[t].cnt;
tree[x].go[idx] = t;
x = t;
}
return ret;
} void dfs_build(int u, int f) {
root[u] = insert(root[f], weight[u]);
for(int p = head[u]; p; p = next[p]) {
int &v = to[p];
if(v == f) continue;
dfs_build(v, u);
}
} int query(int x, int y, int lca, int val) {
int ret = , ret_lca = weight[lca] ^ val;
x = root[x], y = root[y], lca = root[lca];
for(int i = ; i >= ; --i) {
int idx = !((val >> i) & );
int cnt = tree[tree[x].go[idx]].cnt + tree[tree[y].go[idx]].cnt - * tree[tree[lca].go[idx]].cnt;
if(cnt > ) ret |= ( << i);
else idx = !idx;
x = tree[x].go[idx], y = tree[y].go[idx], lca = tree[lca].go[idx];
}
return max(ret, ret_lca);
} int main() {
while(scanf("%d%d", &n, &m) != EOF) {
for(int i = ; i <= n; ++i) scanf("%d", &weight[i]);
init();
for(int i = ; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v, );
}
for(int i = ; i <= m; ++i) Query[i].read(i);
dfs_LCA(, );
init_tree();
dfs_build(, );
for(int i = ; i <= m; ++i)
printf("%d\n", query(Query[i].x, Query[i].y, Query[i].lca, Query[i].z));
}
}
最新文章
- C# Stream
- centos上安装pygame
- jQuery源码分析系列(36) : Ajax - 类型转化器
- Ubuntu1404 (1)
- 前端工作面试问题--摘取自github
- FileUpload1上传控件
- discuz安装与学习资料
- 实现jsp网页设为首页功能
- IBatis.net在asp.net MVC下的使用
- 日均百万 PV 的站点如何做性能监测?试试「3M口罩」!
- C++控制台程序中使用定时器
- MySQL存储过程 CASE语句
- layui弹窗 之 iframe关闭
- Java 测试连接Oracle数据库是否成功,ojdbc7.jar包下载
- luogu2312 [NOIp2015]解方程 (秦九韶)
- Kubernetes Pv &; Pvc
- python-docx 设置标题heading的中文字体类型+设置正文的中文字体类型
- python库:bs4,BeautifulSoup库、Requests库
- eclipse gradle插件 org.gradle.tooling.GradleConnectionException: Could not install Gradle distribution from &#39;https://services.gradle.org/distributions/gradle-3.4-bin.zip&#39;.
- 解决ASP.NET MVC(post数据)Json请求太大,无法反序列化(The JSON request was too large to be deserialized)