題目鏈接：點擊查看

題目大意：給出一顆含有n個節(jié)點的樹，每條邊都有權值，現在給出m個詢問，每次詢問的格式為u,v,w,我們需要求出在路徑u-v上，邊權小于等于w的邊的個數

題目分析：因為一開始不會主席樹，所以就選擇了線段樹+離線處理，因為邊權比較難處理，我就選擇將邊權映射到點權上，這樣就將問題轉換成了求u-v這條路徑上權值小于等于w的點的個數了，因為涉及到了u-v這條路徑，我們需要先將這條鏈拿出來，于是我們就選擇了樹鏈剖分，因為樹上倍增不太適合這個題目，我們后續(xù)還需要對剖分的樹鏈建立線段樹，所以一開始先將給出的數剖一下，然后就是線段樹離線操作的常規(guī)套路了，最后在找u-v這條路的時候一路上維護一下答案即可，有一個細節(jié)需要注意一下，也是zx學長告訴我的，因為這個題目我是將邊權映射到了點權上來處理，也就導致了每個點i代表的其實是點i到點i的父親這一條邊，在樹剖求路徑的時候，在處理最后一段的時候，有一個地方需要加一，不然會WA，這個一會在注釋里我會標記一下

因為這個題目的主流寫法還是主席樹，卑微的我并不會。。所以一會去學習一下主席樹然后再把這個題目寫一遍

代碼：

#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;struct qu {int u,v,w,id;bool operator<(const qu a)const{return w<a.w;} }q[N],edge[N];int ans[N];struct tree {int l,r;int sum; }tree[N<<2];struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int deep[N],fa[N],son[N],num[N];int top[N],id[N],cnt;void dfs1(int u,int f,int dep) {deep[u]=dep;fa[u]=f;son[u]=-1;num[u]=1;for(int i=0;i<node[u].size();i++){int v=node[u][i].to;int w=node[u][i].w;if(v==f)continue;edge[v].id=v;edge[v].w=w;dfs1(v,u,dep+1);num[u]+=num[v];if(son[u]==-1||num[son[u]]<num[v])son[u]=v;} }void dfs2(int u,int f,int root) {id[u]=++cnt;top[u]=root;if(son[u]!=-1)dfs2(son[u],u,root);for(int i=0;i<node[u].size();i++){int v=node[u][i].to;if(v==f||v==son[u])continue;dfs2(v,u,v);} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void update(int k,int pos) {if(tree[k].l==tree[k].r){tree[k].sum=1;return;}int mid=tree[k].l+tree[k].r>>1;if(mid>=pos)update(k<<1,pos);elseupdate(k<<1|1,pos);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }int query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;return query(k<<1,l,r)+query(k<<1|1,l,r); }int solve(int l,int r) {int ans=0;while(top[l]!=top[r]){if(deep[top[l]]<deep[top[r]])swap(l,r);ans+=query(1,id[top[l]],id[l]);l=fa[top[l]];}if(l==r)return ans;if(deep[l]>deep[r])swap(l,r);ans+=query(1,id[l]+1,id[r]);//這里深度小的那個點代表的是該點到該點父親的那條邊，并不屬于u-v這條路徑上，所以需要加一return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);node[u].push_back(Node(v,w));node[v].push_back(Node(u,w));}for(int i=1;i<=m;i++){scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);q[i].id=i;}dfs1(1,0,0);dfs2(1,0,1);sort(q+1,q+1+m);sort(edge+2,edge+1+n);build(1,1,n);int pos=2;//edge數組的下標 for(int i=1;i<=m;i++){while(pos<=n&&edge[pos].w<=q[i].w)update(1,id[edge[pos++].id]);ans[q[i].id]=solve(q[i].u,q[i].v);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; }

?

總結

以上是生活随笔為你收集整理的计蒜客 - Distance on the tree(树链剖分+离线处理+线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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