Tree

 http://acm.hdu.edu.cn/showproblem.php?pid=4757

思路：1.Tarjan求lca ；    2.倍增求lca；

#include <iostream> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <cstdio> #include <map> //#include<bits/stdc++.h> using namespace std; #define sfi(i) scanf("%d",&i) #define sfl(i) scanf("%lld",&i) #define sfs(i) scanf("%s",(i)) #define pri(i) printf("%d\n",i) #define sff(i) scanf("%lf",&i) #define ll long long #define ull unsigned long long #define mem(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f #define eps 1e-10 #define PI acos(-1.0) #define lowbit(x) ((x)&(-x)) #define zero(x) (((x)>0?(x):-(x))<eps) #define fl() printf("flag\n") #define MOD(x) ((x%mod)+mod)%mod #define endl '\n' #define pb push_back #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) /* //--------------------------------------------------------- #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; */ //gp_hash_table<string,int>mp2; //__gnu_pbds::priority_queue<int>q;//因为放置和std重复，故需要带上命名空间 //__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;//最快 //---------------------------------------------------------- //---------------------------------------------------------- const int BufferSize = 1 << 16; char buffer[BufferSize], *_head, *_tail; inline char Getchar() { if (_head == _tail) { int l = fread(buffer, 1, BufferSize, stdin); _tail = (_head = buffer) + l; } return *_head++; } inline int read() { int x = 0, f = 1;char c = Getchar(); for (;!isdigit(c);c = Getchar()) if (c == '-') f = -1; for (;isdigit(c);c = Getchar()) x = x * 10 + c - '0'; return x * f; } //---------------------------------------------------------- const int maxn=1e5+9; const int maxt=3e6+9; const int mod=1e9+7; int tree[maxt][2]; int root[maxt]; int sum[maxt]; int tot; struct E { int to,nex; }edge[maxn<<1]; int head[maxn]; int tot_e; struct Q { int to,nex,w,id; }que[maxn<<1]; int head_q[maxn],a[maxn]; int tot_q; int n,q; bool vis[maxn]; int p[maxn]; int lca[maxn],ans[maxn]; int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); } void addedge(int u,int v) { edge[tot_e].to=v; edge[tot_e].nex=head[u]; head[u]=tot_e++; } void addquery(int u,int v,int w,int id) { que[tot_q].to=v; que[tot_q].nex=head_q[u]; que[tot_q].id=id; que[tot_q].w=w; head_q[u]=tot_q++; } void Tarjan(int u,int fa) { for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(v==fa) continue; Tarjan(v,u); p[v]=u; } vis[u]=1; for(int i=head_q[u];i!=-1;i=que[i].nex) { int v=que[i].to; if(vis[v]) { lca[que[i].id]=Find(v); } } } void Insert(int x,int &y,int val) { y=++tot; sum[y]=sum[x]+1; int now=y; int id; for(int i=16;i>=0;i--) { id=((val>>i)&1); tree[now][id^1]=tree[x][id^1]; tree[now][id]=++tot; now=tree[now][id]; x=tree[x][id]; sum[now]=sum[x]+1; } } int query(int x,int y,int z,int val) { int res=0; int id; int tmp=a[z]; x=root[x]; y=root[y]; z=root[z]; for(int i=16;i>=0;i--) { id=((val>>i)&1); if(sum[tree[y][id^1]]+sum[tree[x][id^1]]-2*sum[tree[z][id^1]]>0) { res=res|(1<<i); y=tree[y][id^1]; x=tree[x][id^1]; z=tree[z][id^1]; } else { y=tree[y][id]; x=tree[x][id]; z=tree[z][id]; } } return max(res,val^tmp); } void dfs(int u,int f) { Insert(root[f],root[u],a[u]); for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(v==f) continue; dfs(v,u); } } void init() { tot=0; tree[0][0]=0; tree[0][1]=0; root[0]=0; mem(head,-1); tot_e=0; mem(head_q,-1); tot_q=0; mem(ans,-1); for(int i=0;i<=n;i++)p[i]=i; mem(sum,0); mem(vis,0); } int main() { //FAST_IO; //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&q)) { init(); for(int i=1;i<=n;i++) { sfi(a[i]); } for(int i=1;i<n;i++) { int u,v; sfi(u); sfi(v); addedge(u,v); addedge(v,u); } dfs(1,0); for(int i=0;i<q;i++) { int x,y; int val; scanf("%d%d%d",&x,&y,&val); addquery(x,y,val,i); addquery(y,x,val,i); } Tarjan(1,0); for(int i=1;i<=n;i++) { for(int j=head_q[i];j!=-1;j=que[j].nex) { int v=que[j].to; int u=i; int id=que[j].id; int w=que[j].w; if(ans[id]!=-1) continue; ans[id]=query(u,v,lca[id],w); } } for(int i=0;i<q;i++) { printf("%d\n",ans[i]); } } return 0; } #include <iostream> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <cstdio> #include <map> //#include<bits/stdc++.h> using namespace std; #define sfi(i) scanf("%d",&i) #define sfl(i) scanf("%lld",&i) #define sfs(i) scanf("%s",(i)) #define pri(i) printf("%d\n",i) #define sff(i) scanf("%lf",&i) #define ll long long #define ull unsigned long long #define mem(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f #define eps 1e-10 #define PI acos(-1.0) #define lowbit(x) ((x)&(-x)) #define zero(x) (((x)>0?(x):-(x))<eps) #define fl() printf("flag\n") #define MOD(x) ((x%mod)+mod)%mod #define endl '\n' #define pb push_back #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) /* //--------------------------------------------------------- #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; */ //gp_hash_table<string,int>mp2; //__gnu_pbds::priority_queue<int>q;//因为放置和std重复，故需要带上命名空间 //__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;//最快 //---------------------------------------------------------- //---------------------------------------------------------- const int BufferSize = 1 << 16; char buffer[BufferSize], *_head, *_tail; inline char Getchar() { if (_head == _tail) { int l = fread(buffer, 1, BufferSize, stdin); _tail = (_head = buffer) + l; } return *_head++; } inline int read() { int x = 0, f = 1;char c = Getchar(); for (;!isdigit(c);c = Getchar()) if (c == '-') f = -1; for (;isdigit(c);c = Getchar()) x = x * 10 + c - '0'; return x * f; } //---------------------------------------------------------- const int maxn=1e5+9; const int maxt=3e6+9; const int mod=1e9+7; int tree[maxt][2]; int root[maxt]; int sum[maxt]; int tot; struct E { int to,nex; }edge[maxn<<1]; int head[maxn]; int tot_e; int fa[maxn][25],deep[maxn],a[maxn]; int n,q; void addedge(int u,int v) { edge[tot_e].to=v; edge[tot_e].nex=head[u]; head[u]=tot_e++; } void Insert(int x,int &y,int val) { y=++tot; sum[y]=sum[x]+1; int now=y; int id; for(int i=16;i>=0;i--) { id=((val>>i)&1); tree[now][id^1]=tree[x][id^1]; tree[now][id]=++tot; now=tree[now][id]; x=tree[x][id]; sum[now]=sum[x]+1; } } int query(int x,int y,int z,int val) { int ans=0; int id; int tmp=a[z]; x=root[x]; y=root[y]; z=root[z]; for(int i=16;i>=0;i--) { id=((val>>i)&1); if(sum[tree[y][id^1]]+sum[tree[x][id^1]]-2*sum[tree[z][id^1]]>0) { ans=ans|(1<<i); y=tree[y][id^1]; x=tree[x][id^1]; z=tree[z][id^1]; } else { y=tree[y][id]; x=tree[x][id]; z=tree[z][id]; } } return max(ans,val^tmp); } void dfs(int u,int f) { Insert(root[f],root[u],a[u]); for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(v==f) continue; fa[v][0]=u; deep[v]=deep[u]+1; dfs(v,u); } } int lca(int x,int y) { if(deep[x]<deep[y]) swap(x,y); int t=deep[x]-deep[y]; for(int i=16;i>=0;i--) { if((t>>i)&1) x=fa[x][i]; } if(x==y) return x; for(int i=16;i>=0;i--) { if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; } //if(x==y) return x; return fa[x][0]; } void init() { tot=0; tree[0][0]=0; tree[0][1]=0; root[0]=0; mem(head,-1); tot_e=0; mem(fa,0); mem(sum,0); deep[1]=0; } int main() { //FAST_IO; //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&q)) { init(); for(int i=1;i<=n;i++) { sfi(a[i]); } for(int i=1;i<n;i++) { int u,v; sfi(u); sfi(v); addedge(u,v); addedge(v,u); } fa[1][0]=0; dfs(1,0); for(int j=1;j<=16;j++) { for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; } while(q--) { int x,y,z; int val; scanf("%d%d%d",&x,&y,&val); z=lca(x,y); printf("%d\n",query(x,y,z,val)); } } return 0; }