HDU - 4757 Tree

Posted on | In , ,

思路

可持久化trie树和主席树的构造类似。这题与之前主席树不同的地方就是在树上建树，类似spoj cot那题。对第n个节点，我们维护根-n这条链上的字典树。然后求x-y路径上的异或最大值时我们用x上的字典树+y上的字典树-两倍lca的父亲的字典树（因为根到lca父亲的字典树加了两遍），然后就是对常规的01字典树的考察。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

const int MAXN=100005,MAX_LOGN=20;
int a[MAXN];

int tree[MAXN*20][2],value[MAXN*20];
int root[MAXN];
int parent[MAX_LOGN][MAXN],depth[MAXN];
int nodecnt,rootcnt;
vector<int> G[MAXN];

int newnode(){
    tree[nodecnt][0]=0,tree[nodecnt][1]=0,value[nodecnt]=0;
    return nodecnt++;
}
void inserts(int pos,int fa,int val){
    int tp=root[pos],tpfa=root[fa];
    for(int i=15;i>=0;i--){
        int c=(val>>i)&1;
        if(!tree[tp][c]){
            int id=newnode();
            tree[tp][c]=id;
            tree[tp][!c]=tree[tpfa][!c];
            value[tree[tp][c]]=value[tree[tpfa][c]];
        }
        tp=tree[tp][c],tpfa=tree[tpfa][c];
        value[tp]++;
    }
}
int query(int x,int y,int xylca,int val){
    int posx=root[x],posy=root[y],poslca,ans=0;
    poslca=parent[0][xylca]==-1?0:root[parent[0][xylca]];
    for(int i=15;i>=0;i--){
        int c=(val>>i)&1;
        if(value[tree[posx][!c]]+value[tree[posy][!c]]-2*value[tree[poslca][!c]]>0){
            ans|=(1<<i);
            c=!c;
        }
        posx=tree[posx][c],posy=tree[posy][c],poslca=tree[poslca][c];
    }
    return ans;
}
void dfs(int u,int fa,int d){
    root[u]=newnode();
    inserts(u,fa,a[u]);
    parent[0][u]=fa,depth[u]=d;
    for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++){
        if(*it!=fa)dfs(*it,u,d+1);
    }
}
void init(int V){
    dfs(1,-1,0);
    for(int k=0;k+1<MAX_LOGN;k++){
        for(int v=1;v<=V;v++){
            if(parent[k][v]<0)parent[k+1][v]=-1;
            else parent[k+1][v]=parent[k][parent[k][v]];
        }
    }
}
int lca(int u,int v){
    if(depth[u]>depth[v])swap(u,v);
    for(int k=0;k<MAX_LOGN;k++){
        if((depth[v]-depth[u])>>k&1){
            v=parent[k][v];
        }
    }
    if(u==v)return u;
    for(int k=MAX_LOGN-1;k>=0;k--){
        if(parent[k][u]!=parent[k][v]){
            u=parent[k][u];
            v=parent[k][v];
        }
    }
    return parent[0][u];
}

int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int u,v,x,y,z;
        root[0]=0;
        tree[0][0]=0,tree[0][1]=0,value[0]=0;
        nodecnt=1,rootcnt=1;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v),G[v].push_back(u);
        }
        init(n);
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&x,&y,&z);
            printf("%d\n",query(x,y,lca(x,y),z));
        }
        for(int i=0;i<MAXN;i++)G[i].clear();
    }
	return 0;
}