tree
Time Limit: 8000ms
Memory Limit: 262144KB
This problem will be judged on HDU. Original ID: 5390
64-bit integer IO format: %I64d Java class name: Main
Given a rooted tree(node 1 is the root) with n nodes. The ithnode has a positive value vi at beginning.
We define the universal set S includes all nodes.
There are two types of Memphis's operation.
First, Memphis may change the value of one node. It's the first type operation:
We define the universal set S includes all nodes.
There are two types of Memphis's operation.
First, Memphis may change the value of one node. It's the first type operation:
0 u v (u∈S,0≤v≤109)
What's more, Memphis wants to know what's the maxinum of vu⊗vt(t∈path(u,root),⊗ means xor) . It's the second type operation:
1 u (u∈S)
Input
This problem has multi test cases(no more than 3).
The first line contains a single integer T, which denotes the number of test cases.
For each test case,the first line contains two non-negative integer n,m(1≤n,m≤100000) - the number of nodes and operations.
The second line contains n−1 non-negative integer f2∼fn(fi<i) - the father of ithnode.
The third line contains n non-negative integer v1∼vn(0≤vi≤109) - the value of nodes at beginning.
Follow m lines describe each operation.
The first line contains a single integer T, which denotes the number of test cases.
For each test case,the first line contains two non-negative integer n,m(1≤n,m≤100000) - the number of nodes and operations.
The second line contains n−1 non-negative integer f2∼fn(fi<i) - the father of ithnode.
The third line contains n non-negative integer v1∼vn(0≤vi≤109) - the value of nodes at beginning.
Follow m lines describe each operation.
Output
For each test cases,for each second operation print a non-negative integer.
Sample Input
1
10 10
1 1 2 2 3 1 2 3 5
23512 460943 835901 491571 399045 97756 413210 800843 283274 106134
0 7 369164
0 7 296167
0 6 488033
0 7 187367
0 9 734984
1 6
0 5 329287
1 5
0 7 798656
1 10
Sample Output
766812
351647
431641
Source
解题：看到这位大神的代码后，看了一上午，终于看明白了，真的很神，离线做法，统一查询
先说说为什么要用线段树，因为我们发现是树，树任意两点之间只有唯一的路径，dfs序列，然后更新以后，为什么没有放到叶子结点？因为这是父节点，其代表区间内的任意节点到根的路径，必须经过父节点
所以当然是挂在区间上，而不是放到叶子，那么查询情况呢？我们是从根一直到叶子结点，一直路径上经过的结点，都把查询加入了，因为要查询的结点到根，也是必须经过这些结点的
那么字典树所谓何用，字典树是用来快速求解异或最大值的，利用的是贪心的思想，优先让高位变成1
好啦！代码已经灰常灰常灰常清晰了。。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int maxn = ;
struct arc{
int to,next;
arc(int x = ,int y = -){
to = x;
next = y;
}
}e[maxn<<];
struct node{
int val,foo,op;
node(int x = ,int y = ,int z = ){
val = x;
foo = y;
op = z;
}
};
struct trie{
int tot,root,b[maxn*][],cnt[maxn*];
int newnode(){
b[tot][] = b[tot][] = cnt[tot] = ;
return tot++;
}
void init(){
tot = ;
root = newnode();
}
void insert(int val,int f,int root){
for(int i = ; i >= ; --i){
int bt = ((val>>i)&);
int &son = bt?b[root][]:b[root][];
if(!son) son = newnode();
root = son;
cnt[root] += f;
}
}
int query(int val,int root,int ret = ){
for(int i = ; i >= ; --i){
int bt = ((val>>i)&);
int son[] = {b[root][],b[root][]};
if((!son[] || !cnt[son[]]) && (!son[] || !cnt[son[]])) return ;
if(son[bt] && cnt[son[bt]]){
ret |= (<<i);
root = son[bt];
}else root = son[bt^];
}
return ret;
}
}T;
int head[maxn],L[maxn],R[maxn],ans[maxn],tot,times;
vector<node>g[maxn<<];
void add(int u,int v){
e[tot] = arc(v,head[u]);
head[u] = tot++;
}
void dfs(int u){
L[u] = ++times;
for(int i = head[u]; ~i; i = e[i].next) dfs(e[i].to);
R[u] = times;
}
void build(int L,int R,int v){
g[v].clear();
if(L == R) return;
int mid = (L + R)>>;
build(L,mid,v<<);
build(mid+,R,v<<|);
}
void update(int L,int R,int lt,int rt,int val,int f,int v){
if(lt <= L && rt >= R){
g[v].push_back(node(val,f,));
return;
}
int mid = (L + R)>>;
if(lt <= mid) update(L,mid,lt,rt,val,f,v<<);
if(rt > mid) update(mid+,R,lt,rt,val,f,v<<|);
}
void query(int L,int R,int p,int val,int id,int v){
g[v].push_back(node(val,id,));
if(L == R) return;
int mid = (L + R)>>;
if(p <= mid) query(L,mid,p,val,id,v<<);
else query(mid+,R,p,val,id,v<<|);
}
int val[maxn];
void query(int L,int R,int v){
T.init();
for(int i = ,sz = g[v].size(); i < sz; ++i){
if(g[v][i].op == ) T.insert(g[v][i].val,g[v][i].foo,T.root);
else ans[g[v][i].foo] = max(ans[g[v][i].foo],T.query(g[v][i].val,T.root));
}
if(L == R) return;
int mid = (L + R)>>;
query(L,mid,v<<);
query(mid+,R,v<<|);
}
int main(){
int kase,n,m,fa,op,w;
scanf("%d",&kase);
while(kase--){
scanf("%d%d",&n,&m);
memset(head,-,sizeof head);
times = tot = ;
for(int i = ; i <= n; ++i){
scanf("%d",&fa);
add(fa,i);
}
dfs();
build(L[],R[],);
for(int i = ; i <= n; ++i){
scanf("%d",val+i);
update(,n,L[i],R[i],val[i],,);
}
for(int i = ; i <= m; ans[i++] = -){
scanf("%d",&op);
if(op){
scanf("%d",&fa);
query(,n,L[fa],val[fa],i,);
}else{
scanf("%d%d",&fa,&op);
update(,n,L[fa],R[fa],val[fa],-,);
val[fa] = op;
update(,n,L[fa],R[fa],op,,);
}
}
query(,n,);
for(int i = ; i <= m; ++i)
if(ans[i] != -) printf("%d\n",ans[i]);
}
return ;
}