2017ACM/ICPC广西邀请赛 K- Query on A Tree trie树合并
Query on A Tree
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once.
Monkey A gave a value to each node on the tree. And he was curious about a problem.
The problem is how large the xor result of number x and one node value of label y can be, when giving you a non-negative integer x and a node label u indicates that node y is in the subtree whose root is u(y can be equal to u).
Can you help him?
For each test case there are two positive integers n and q, indicate that the tree has n nodes and you need to answer q queries.
Then two lines follow.
The first line contains n non-negative integers V1,V2,⋯,Vn, indicating the value of node i.
The second line contains n-1 non-negative integers F1,F2,⋯Fn−1, Fi means the father of node i+1.
And then q lines follow.
In the i-th line, there are two integers u and x, indicating that the node you pick should be in the subtree of u, and x has been described in the problem.
2≤n,q≤105
0≤Vi≤109
1≤Fi≤n, the root of the tree is node 1.
1≤u≤n,0≤x≤109
1 2
1
1 3
2 1
题解:
每个数存在各自trie树里边,n个点这是棵树,再从底向上tri树合并起来
查询就是查询一颗合并后的trie树,利用从高位到低位,贪心取
#include <bits/stdc++.h>
inline int read(){int x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}return x*f;} using namespace std; #define LL long long
const int N = 2e5; vector<int > G[N];
int n, q, x, u, a[N];
int ch[N*][], root[N],sz; void inserts(int u,int x) {
root[u] = ++sz;
int tmp = sz;
int y = sz;
for(int i = ; i >= ; --i) {
int tmps = (x>>i)&;
if(!ch[y][tmps]) ch[y][tmps] = ++sz;
y = ch[y][tmps];
}
}
int merges(int u,int to) {
if(u == ) return to;
if(to == ) return u;
int t = ++sz;
ch[t][] = merges(ch[u][],ch[to][]);
ch[t][] = merges(ch[u][],ch[to][]);
return t;
}
void dfs(int u) {
inserts(u,a[u]);
for(auto to:G[u]) {
dfs(to);
root[u] = merges(root[u],root[to]);
}
}
LL query(int u,int x) {
int y = root[u];
LL ret = ;
for(int i = ; i >= ; --i) {
int tmps = (x>>i)&;
if(ch[y][tmps^]) ret += (<<i),y = ch[y][tmps^];
else y = ch[y][tmps];
}
return ret;
}
void init() {
for(int i = ; i <= n; ++i) root[i] = ,G[i].clear();
sz = ;
memset(ch,,sizeof(ch));
}
int main( int argc , char * argv[] ){
while(scanf("%d%d",&n,&q)!=EOF) {
for(int i = ; i <= n; ++i) scanf("%d",&a[i]);
init();
for(int i = ; i <= n; ++i) {
scanf("%d",&x);
G[x].push_back(i);
}
dfs();
for(int i = ; i <= q; ++i) {
scanf("%d%d",&u,&x);
printf("%lld\n",query(u,x));
}
}
return ;
}
最新文章
- android开发 兵器
- 已知一个日期和天数, 求多少天后的日期(是那个超时代码的AC版)
- jsp 环境配置记录
- AmazeUI基本样式
- 5. c++ 内存管理 C/C++ 内存机制
- 使用jquery.form异步提交注意jquery.validate需要手动添加验证
- VBS基本语法
- 《Java编程思想》第一二章
- SQL语句Tips
- java之基础数据类型学习————(一)
- 27.app后端搭建聊天服务器的经历
- 20190322-a标签、img标签、三列表、特殊字符实体、表格
- python 包下载地址
- hive条件过滤
- Sqlserver 数据库定时自动备份
- 5种必会的Java异步调用转同步的方法你会几种
- 50个常用的sql语句
- es6/ts for in/ for of
- cout的输出格式初探3
- 【C#/WPF】保存BitmapImage数据到文件中
热门文章
- 九度oj 题目1099:后缀子串排序
- gitlab简介配置和参数修改
- 【Android】android:ellipsize的使用以及一个点解决方法
- Luogu【P3609】蹄子剪刀布(DP+滚动数组)
- MyEclipse6.5增加对Tomcat7的支持
- 438. Find All Anagrams in a Strin
- GoldenDict词典下载安装
- BZOJ——1720: [Usaco2006 Jan]Corral the Cows 奶牛围栏
- Java ListIterator 与 Iterator 异同
- 问题:typedef char *pstring????