題目鏈接：點擊查看

題目大意：給出一棵樹，每條邊上都有一個權值，給出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都在一條重鏈上，剛才我們已經將一條重鏈上的點都重新編號，并讓他們挨在一起了，所以我們現在只需要查詢點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(树链剖分+线段树+离线处理)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。