題目鏈接：點擊查看

題目大意：給出一棵有有n個節(jié)點的樹，每個點都有一個權值，現(xiàn)在給出m個查詢，每次查詢的形式為：x,y,z，求出從點x到點y的路徑上任選一點，使其與z的異或值最大，輸出異或值

題目分析：一開始看到從一個區(qū)間內(nèi)任選一個點與指定的值異或取最值，立馬就想到了可持久化trie樹，可是這個題目是基于樹上操作的，我們該怎么將樹上的路徑拿下來呢？其實這就涉及到了LCA，在給出兩個點x和y后，只需要求出兩個點的lca，就可以將x到y(tǒng)的路徑分為了x到lca的路徑+y到lca的路徑了，由于lca的深度肯定小于等于x和y中的任何一個值，所以我們就可以將x到y(tǒng)的路徑分為兩個區(qū)間了：[lca,x]和[lca,y]，這樣就能使兩個算法配合操作了

關于在樹上建可持久化字典樹，我們只需要從根節(jié)點開始遍歷，然后每次利用父節(jié)點的root繼承就可以了，因為我們需要的區(qū)間是

[lca,x]和[lca,y]，而可持久化的數(shù)據(jù)結構可以當做前綴和來理解，所以最后我們提供的點應該是[fa[lca],x]和[fa[lca],y]，fa數(shù)組代表的是當前節(jié)點的父節(jié)點，這樣就能達到前綴和作差的形式了

通過這個題真的學到了很多，先是拋開所需要的算法lca和可持久化字典樹不說，首先也是默寫代碼的一種能力，然后是調(diào)試的能力，因為一開始把lca函數(shù)中的deep[a]和deep[b]寫反了導致樣例都跑不出來，還有就是對各個函數(shù)更加理解了，在調(diào)試的過程中，親手將一個遞歸程序換成了循環(huán)來寫，也是更進一步的理解了可持久化字典樹這個數(shù)據(jù)結構吧，也不枉我調(diào)了三個小時，期間和zx學長學到了好多比較先進的知識，首先在初始化時不需要用memset對trie和sum兩個比較大的數(shù)組直接初始化，我們可以定義一個newnode函數(shù)，用來在使用之前初始化這兩個數(shù)組，還有就是在求lca時，可以稍微暴力一點，也暴力不到那里去，一開始定義的范圍可以根據(jù)n來確定，下限是0毋庸置疑，上限我們可以設置為log2(n)+1，這樣的話可以保證對于較小程序的合理性

不多說了，上代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m;int head[N];int a[N];//每個點的權值 int deep[N],fa[N];//每個點的深度和父節(jié)點 int dp[N][20];//倍增 int trie[N*17][2];//字典樹 int sum[N*17];int root[N];int cnt,tot,k;struct edge {int to,next; }edge[N*2];void addedge(int u,int v) {edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;edge[tot].to=u;edge[tot].next=head[v];head[v]=tot++; }int LCA(int a,int b) {if(deep[a]<deep[b])swap(a,b);for(int i=k;i>=0;i--)if(deep[a]-deep[b]>=(1<<i))a=dp[a][i];if(a==b)return a;for(int i=k;i>=0;i--)if(dp[a][i]!=dp[b][i]){a=dp[a][i];b=dp[b][i];}return dp[a][0]; }int newnode() {cnt++;trie[cnt][0]=trie[cnt][1]=0;sum[cnt]=0;return cnt; }void insert(int pre,int &cur,int step,int x) {cur=newnode();trie[cur][0]=trie[pre][0];trie[cur][1]=trie[pre][1];sum[cur]=sum[pre]+1;if(step<0)return;int to=(x>>step)&1;insert(trie[pre][to],trie[cur][to],step-1,x); }int query(int l,int r,int step,int x) {if(step<0)return 0;int to=(x>>step)&1;if(sum[trie[r][!to]]-sum[trie[l][!to]]>0)return query(trie[l][!to],trie[r][!to],step-1,x)+(1<<step);elsereturn query(trie[l][to],trie[r][to],step-1,x); }void dfs(int u,int f,int dep) {insert(root[f],root[u],15,a[u]);deep[u]=dep;fa[u]=f;dp[u][0]=f;for(int i=1;i<=k;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(v==f)continue;dfs(v,u,dep+1);} }void init() {memset(head,-1,sizeof(head));cnt=0;tot=0;k=log2(n)+1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);}dfs(1,0,0);while(m--){int u,v,x;scanf("%d%d%d",&u,&v,&x);int lca=LCA(u,v);printf("%d\n",max(query(root[fa[lca]],root[u],15,x),query(root[fa[lca]],root[v],15,x)));}}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 4757 Tree(LCA+可持久化trie树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。