HDU - 3804 Query on a tree(树链剖分+线段树+离线处理)
題目鏈接:點擊查看
題目大意:給出一棵樹,每條邊上都有一個權值,給出m個查詢:a,b:問從點1到點a的唯一路徑上,在邊權小于等于b的邊中選出邊權最大的值輸出,若沒有符合條件的邊則輸出-1;
題目分析:如果還不清楚樹鏈剖分,這里有一個講的很棒的博客:點擊查看
然后看到這里就默認已經掌握了樹鏈剖分和線段樹的基礎知識了。
下面分析一下這個題目的思路,題目很好理解,但如果直接暴力模擬的話必定超時,所以我們應該轉換為logn級別的復雜度再下手,關于求不超過一個值的這種題,之前我做過一個不在樹上的,是問瑪麗奧能跳多高的一個題,用到的方法是離線處理,然后給查詢按照高度排序,最后根據根據從低到高遍歷,每次加入不超過此次高度的點,用線段樹維護數量即可,這個題目也是類似,因為最后要求的是滿足條件的最大值,所以我們可以用線段樹維護區間內的最大值,然后為了讓所得到的結果都能滿足條件,我們可以先將m個查詢儲存下來,離線處理,按照權值從小到大排序,每次插入小于等于該權值的邊,然后再用線段樹查詢區間即可,思路是有了,我們接下來的問題就是,如何將剛才的思路在樹上實現呢,因為學習了dfs序,學會了可以將樹上的點轉化為線性的已知條件來使用,但dfs序的前提是必須是有關于祖先和子節點的問題,而這個題目的前提是必須在樹上的一條鏈上。
所以這篇博客一開始我就讓大家先學習了一下樹鏈剖分的知識。樹鏈剖分,顧名思義,就是將一棵樹,分成一條一條的鏈子,這樣就形成了一種線性結構,就可以利用上面的思路在樹上實現了。我在大體的講一下如何在樹上用樹鏈剖分來實現這個題目:
首先,我們先用樹鏈剖分,找出每條重鏈,然后依據重鏈的順序,依次給每個點進行重新編號,讓每條重鏈上的點都挨在一起,這樣的目的就是方便使用線段樹進行查詢。然后再用一個輔助數組記錄每條重鏈的端點,也就是每條重鏈上深度最小的那個點,如果一條重鏈上只有一個點,那么該點的端點就是它本身。我們現在已經完成這兩個操作后就可以利用線段樹進行模擬了,因為我們經過樹鏈剖分的處理后,每個節點都獲得了一個全新的序號,那么我們按照新的序號進行建樹,接下來的所有操作,無論是查詢還是更新,都是基于新的序號來處理的,這里務必要理解!!接著按照上述思路進行,首先要對每條邊進行處理,因為權值都在邊上,我們不太好操作,所以我們將權值轉移到點上,轉移到終點上即可,比如u->v的權值為w,那么就記為點v的權值為w,然后對m個查詢先儲存下來并排序處理,隨后遍歷一遍每個查詢,然后將小于等于該查詢的點加入到線段樹中,意思就是將權值小于等于該查詢的點加入到線段樹中,更新最大值,等到權值小于等于該查詢的所有點都已經加入到線段樹中后,對該查詢進行求結果的處理,我們該怎么求結果呢?因為如果放在樹上來說,起點是點1,終點是查詢中的點a,那么我們需要遍歷一邊點1到點a的路徑(路徑一定是唯一的),掃一遍路徑并維護最大值即可,那么我們首先要確定點a和點1的關系,即點a和點1是否在一條重鏈上,因為點1是整棵樹的根節點,所以點1的端點就是1,我們先看一下點a的端點是什么:
如果點a的端點不是點1,那么說明點a和點1不在一條重鏈上,我們可以先沿著點a走到點a的端點上,然后在走到端點的父節點上,然后在順著走到端點的父節點的端點上,以此類推一直往上走,直到走到點1為止,這段路徑一定是唯一的
因為無論很麻煩的走,還是很簡單的走,點a到點1的路徑都是唯一的(因為在樹上兩點之間的路徑一定是唯一的),又因為每條重鏈上的點的編號都是相互挨著的,所以當我們在每條重鏈上經過的時候,都可以利用線段樹來查詢這段路上滿足條件的最大值,直到走到點1為止,這樣最后的答案就一定是一路上維護而來的最大值了。
對了,這個題目中好像不需要記錄深度這個屬性,因為點1作為起點,它的深度一定是最小的,因為是總根節點嘛,不過寫都寫了,就當是練習了一下樹鏈剖分的模板吧-.-
一定要記住!!要用新的編號來建樹,用新的編號來操作!!剛學樹鏈剖分的時候就是這里不太理解,導致看別人的例程都看不懂。。上代碼了,更多的細節在注釋中解釋:
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100; /***************************************************************************/ //以下是簡單的線段樹維護最大值,不多解釋了,點更新+區間查詢 //因為不習慣寫類,還是都拆散開都把函數放到外面來舒服點 struct vvv {int id,w;bool operator<(vvv a)const{return w<a.w;} }val[N];struct Node {int l,r,mmax; }tree[N<<2];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].mmax=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void pushup(int k) {tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); }void update(int k,int pos,int val) {if(tree[k].l==tree[k].r){tree[k].mmax=val;return;}int mid=tree[k].l+tree[k].r>>1;if(mid>=pos)update(k<<1,pos,val);elseupdate(k<<1|1,pos,val);pushup(k); }int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].mmax;return max(query(k<<1,l,r),query(k<<1|1,l,r)); } //線段樹到此為止 /***************************************************************************/ struct edge {int u,v,w;bool operator<(edge a)const{return w<a.w;} }edge[N];//結構體存邊,用于在給每個節點重新編號后,給其賦權值vector<int>node[N];//vector存邊int num[N],son[N],fa[N],deep[N];//num:子樹大小,son:重兒子,fa:父節點,deep:深度void dfs1(int u,int f,int d)//求fa,num,deep,son {num[u]=1;fa[u]=f;deep[u]=d;son[u]=0;for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==f)continue;dfs1(v,u,d+1);num[u]+=num[v];if(!son[u]||num[son[u]]<num[v]){son[u]=v;}} }int top[N],id[N],cnt;//top:重鏈的端點,id:全新的編號void dfs2(int u,int root)//求top,id {top[u]=root;id[u]=++cnt;if(son[u])dfs2(son[u],root);for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==son[u]||v==fa[u])continue;dfs2(v,v);} } struct qu {int id,w,ind,ans;//id:第幾個查詢,w:查詢的權值,ind:查詢的點,ans:查詢的結果bool operator<(qu a)const{return w<a.w;} }ans[N];//存查詢信息int solve(int pos)//掃一遍對于查詢的點到達點1的路徑,并維護最大值 {int ans=0;while(top[pos]!=1)//如果不在同一條重鏈上{ans=max(ans,query(1,id[top[pos]],id[pos]));//維護目前重鏈上的最大值pos=fa[top[pos]];//走到父節點所在的重鏈上}ans=max(ans,query(1,id[top[pos]],id[pos]));//當點pos和點1處于同一條重鏈后會跳出while,所以最后需要再維護一下最大值if(ans==0)//別忘了如果不符合條件返回-1return -1;elsereturn ans; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<n;i++)//存邊{int u,v,w;scanf("%d%d%d",&u,&v,&w);edge[i].u=u;edge[i].v=v;edge[i].w=w;node[u].push_back(v);node[v].push_back(u);}dfs1(1,-1,1);cnt=0;dfs2(1,1);int q;scanf("%d",&q);for(int i=1;i<=q;i++)//存查詢{scanf("%d%d",&ans[i].ind,&ans[i].w);ans[i].id=i;}sort(ans+1,ans+1+q);//排序離線處理for(int i=1;i<n;i++){int u=edge[i].u;int v=edge[i].v;int w=edge[i].w;if(deep[u]>deep[v])swap(u,v);val[id[v]].id=id[v];val[id[v]].w=w;}sort(val+2,val+n+1);//不包含點1的其余n-1個點int t=2;build(1,1,n);for(int i=1;i<=q;i++){int w=ans[i].w;int id=ans[i].id;while(val[t].w<=w&&t<=n)//注意這里判斷邊界,一個是判斷小于等于查詢權值,一個是判斷t不能越界{update(1,val[t].id,val[t].w);t++;}ans[id].ans=solve(ans[i].ind);} for(int i=1;i<=q;i++)printf("%d\n",ans[i].ans);}return 0; }?
總結
以上是生活随笔為你收集整理的HDU - 3804 Query on a tree(树链剖分+线段树+离线处理)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: HDU - 5692 Snacks(df
- 下一篇: POJ - 3263 Tallest C