Count on a tree 树上主席树-白红宇的个人博客

Count on a tree 树上主席树

发布日期：2021-09-25 23:58:05 浏览次数：8 分类：技术文章

本文共 2683 字，大约阅读时间需要 8 分钟。

此代码在原 oj ac ，在某谷re全家福。

裸的板子，调了4个小时了快，某谷还是re，给跪了，蒟蒻求助。

两个题有一点点区别，某谷输入数据是加密的，vj是直接输入的。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=100010,M=300020,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;int a[N],fa[N][30],depth[N];int e[M],ne[M],h[N],idx;int root[M],tot;vector
                
                 v;struct Node{ int l,r; int cnt;}tr[N*30];void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++;}int find(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin();}void bfs(){ memset(depth,0x3f,sizeof (depth)); depth[0]=0; depth[1]=1; queue
                 
                  q; q.push(1); while(q.size()) { int t=q.front(); q.pop(); for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(depth[j]>depth[t]+1) { depth[j]=depth[t]+1; q.push(j); fa[j][0]=t; for(int k=1;k<=19;k++) fa[j][k]=fa[fa[j][k-1]][k-1]; } } }}int lca(int a,int b){ if(depth[a]
                  
                   =0;i--) if(depth[fa[a][i]]>=depth[b]) a=fa[a][i]; if(a==b) return a; for(int i=19;i>=0;i--) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i]; return fa[a][0];}int build(int l,int r){ int p=++tot; tr[p].cnt=0; if(l==r) return p; int mid=l+r>>1; tr[p].l=build(l,mid); tr[p].r=build(mid+1,r); return p;}int insert(int p,int l,int r,int x){ int q=++tot; tr[q]=tr[p]; if(l==r) { tr[q].cnt++; return q; } int mid=l+r>>1; if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x); else tr[q].r=insert(tr[p].r,mid+1,r,x); tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt; return q;}void dfs(int u,int f){ root[u]=insert(root[f],0,v.size()-1,find(a[u])); for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==f) continue; dfs(j,u); }}int query(int x,int y,int p,int q,int l,int r,int k){ if(l==r) return l; int cnt=tr[tr[x].l].cnt+tr[tr[y].l].cnt-tr[tr[p].l].cnt-tr[tr[q].l].cnt; int mid=l+r>>1; if(k<=cnt) return query(tr[x].l,tr[y].l,tr[p].l,tr[q].l,l,mid,k); else return query(tr[x].r,tr[y].r,tr[p].r,tr[q].r,mid+1,r,k-cnt);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); memset(h,-1,sizeof (h)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),v.pb(a[i]); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); root[0]=build(0,v.size()-1); dfs(1,0); bfs(); int last=0; for(int i=1;i<=m;i++) { int u,e,k; scanf("%d%d%d",&u,&e,&k); int x=lca(u,e); int ans=v[query(root[u],root[e],root[x],root[fa[x][0]],0,v.size()-1,k)]; printf("%d\n",ans); last=ans; } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/108314024 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：P4462 异或序列莫队 + 异或技巧

下一篇：Educational Codeforces Round 36 (Rated for Div. 2) E 线段树 || 珂朵莉树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章