題目鏈接：點擊查看

題目大意：給出一棵樹，每個點都有一個權(quán)值，現(xiàn)在給出m個詢問，每次詢問的格式是u,v,k，要求輸出u-v這條路徑上第k大的數(shù)

題目分析：一看到第k大的數(shù)就會想到主席樹，既然是在樹上的操作，我們就需要用lca先把u-v這條路拿出來，具體的還是用樹上倍增來實現(xiàn)，然后在dfs的過程中建立一棵可持久化的線段樹，也就是主席樹，在查詢的時候就可以直接對于u-lca-v這條路上直接查詢了，（也是學(xué)到了，本來以為要拆成u-lca和lca-v兩條路查詢，然后就不知所措了。。）不過這個題有個挺惡心的坑，就是沒給數(shù)據(jù)范圍，經(jīng)過測試后給出的數(shù)會比我以往設(shè)置的inf(0x3f3f3f3f)還要大，因為主席樹本身所具有的離散化的特性，我將l,r,mid的數(shù)據(jù)范圍改為longlong之后就A了，或者直接干脆一點，離散化一下就什么問題都沒了，因為數(shù)據(jù)只給了1e5，離散化后主席樹也只用開1e5*20就夠了，如果不離散化的話得開到1e5*32才行，大概就是這樣吧，兩份代碼差不多，都掛一下吧：

離散化：

#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> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int limit;//樹上倍增用vector<int>num;//離散化用int a[N];//儲存權(quán)值vector<int>node[N];//鄰接表int dp[N][20],deep[N];//樹上倍增用struct tree {int l,r,sum; }tree[N*20];//主席樹用int root[N],cnt;//主席樹用int getnum(int x)//二分映射離散化后的下標(biāo) {return lower_bound(num.begin(),num.end(),x)-num.begin(); }void insert(int pre,int& cur,int l,int r,int pos)//主席樹插入 {cur=++cnt;tree[cur]=tree[pre];tree[cur].sum++;if(l==r)return;int mid=l+r>>1;if(mid>=pos)insert(tree[pre].l,tree[cur].l,l,mid,pos);elseinsert(tree[pre].r,tree[cur].r,mid+1,r,pos); }int query(int u,int v,int lca,int lca_fa,int l,int r,int k)//主席樹詢問 {if(l==r)return l;int d=tree[tree[u].l].sum+tree[tree[v].l].sum-tree[tree[lca].l].sum-tree[tree[lca_fa].l].sum;//求一下左子樹還有多少個元素int mid=l+r>>1;if(d>=k)return query(tree[u].l,tree[v].l,tree[lca].l,tree[lca_fa].l,l,mid,k);elsereturn query(tree[u].r,tree[v].r,tree[lca].r,tree[lca_fa].r,mid+1,r,k-d); }void dfs(int u,int f,int dep)//樹的遍歷 {insert(root[f],root[u],0,num.size(),getnum(a[u]));deep[u]=dep;dp[u][0]=f;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==f)continue;dfs(v,u,dep+1);} }int LCA(int x,int y)//求lca {if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0]; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);limit=log2(n);for(int i=1;i<=n;i++){scanf("%d",a+i);num.push_back(a[i]);}sort(num.begin(),num.end());num.erase(unique(num.begin(),num.end()),num.end());for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}dfs(1,0,0);while(m--){int u,v,k;scanf("%d%d%d",&u,&v,&k);int lca=LCA(u,v);printf("%d\n",num[query(root[u],root[v],root[lca],root[dp[lca][0]],0,num.size(),k)]);}return 0; }

不離散化：

#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> using namespace std;typedef long long LL;const int inf=INT_MAX;//inf開到最大const int N=1e5+100;int limit;int a[N];vector<int>node[N];int dp[N][20],deep[N];struct tree {int l,r,sum; }tree[N*32];//注意這里，不離散化的話需要開到1e5*32int root[N],cnt;void insert(int pre,int& cur,LL l,LL r,int pos) {cur=++cnt;tree[cur]=tree[pre];tree[cur].sum++;if(l==r)return;LL mid=l+r>>1;//mid，l，r都要開longlong，下同if(mid>=pos)insert(tree[pre].l,tree[cur].l,l,mid,pos);elseinsert(tree[pre].r,tree[cur].r,mid+1,r,pos); }int query(int u,int v,int lca,int lca_fa,LL l,LL r,int k) {if(l==r)return l;int d=tree[tree[u].l].sum+tree[tree[v].l].sum-tree[tree[lca].l].sum-tree[tree[lca_fa].l].sum;LL mid=l+r>>1;if(d>=k)return query(tree[u].l,tree[v].l,tree[lca].l,tree[lca_fa].l,l,mid,k);elsereturn query(tree[u].r,tree[v].r,tree[lca].r,tree[lca_fa].r,mid+1,r,k-d); }void dfs(int u,int f,int dep) {insert(root[f],root[u],1,inf,a[u]);deep[u]=dep;dp[u][0]=f;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==f)continue;dfs(v,u,dep+1);} }int LCA(int x,int y) {if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0]; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);limit=log2(n);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);node[u].push_back(v);node[v].push_back(u);}dfs(1,0,0);while(m--){int u,v,k;scanf("%d%d%d",&u,&v,&k);int lca=LCA(u,v);printf("%d\n",query(root[u],root[v],root[lca],root[dp[lca][0]],1,inf,k));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的SPOJ - COT Count on a tree(LCA+主席树+离散化)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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