題目鏈接：點擊查看

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

題目分析：多的不說了，上一個博客都寫的差不多了，這次來掛一發主席樹+LCA的代碼，LCA我覺得樹上倍增的好寫，反正寫起來不容易錯，然后前兩天學會了可持久化字典樹之后，再回頭看主席樹也覺得簡簡單單了

對了，注意一下主席樹的大小，要開nlogn，一般的題目都超不過1e6，所以主席樹都開N*20就足夠了，但這個題目我懶得離散化，直接用了1-inf做上下限，所以主席樹大概需要開1e5*32才夠，不然會RE

這里就說一下吧，普通的線段樹若是用值做區間的話，肯定是需要離散化的，不然根本開不了那么大，但主席樹本身插點就是有點離散化的意思，因為本身的區間就是不連續的，加上動態開點，時間復雜度就是稍微多了那么一丟丟，也就是log(1e5)和log(1e9)之間的區別，所以就直接往主席樹上亂搞就是了

代碼：

#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 Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int dp[N][20],deep[N],limit;//樹上倍增求lca所需要的數組struct tree {int l,r,sum; }tree[N*32];//主席樹int root[N],cnt=0;//主席樹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 pre,int cur,int l,int r,int ll,int rr)//主席樹查詢,l,r:當前區間,ll,rr:目標區間 {if(l>=ll&&r<=rr)return tree[cur].sum-tree[pre].sum;if(r<ll||l>rr)return 0;int mid=l+r>>1;return query(tree[pre].l,tree[cur].l,l,mid,ll,rr)+query(tree[pre].r,tree[cur].r,mid+1,r,ll,rr); }void dfs(int u,int f,int dep) {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].to;int w=node[u][i].w;if(v==f)continue;insert(root[u],root[v],1,inf,w);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)+1;for(int i=1;i<n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a].push_back(Node(b,c));node[b].push_back(Node(a,c));}dfs(1,0,0);while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);int lca=LCA(u,v);printf("%d\n",query(root[lca],root[u],1,inf,0,w)+query(root[lca],root[v],1,inf,0,w));}return 0; }

?

總結

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

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