BZOJ 2588: Spoj 10628. Count on a tree-可持久化线段树+LCA(点权)(树上的操作) 无语(为什么我的LCA的板子不对)...-白红宇

BZOJ 2588: Spoj 10628. Count on a tree-可持久化线段树+LCA(点权)(树上的操作) 无语(为什么我的LCA的板子不对)...

阅读量：4969 次

发布时间：2019-06-12

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

Time Limit: 12 Sec Memory Limit: 128 MB

Submit: 9280 Solved: 2421

[][][]

Description

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

Input

第一行两个整数N,M。

第二行有N个整数，其中第i个整数表示点i的权值。

后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。

最后M行每行两个整数(u,v,k)，表示一组询问。

Output

M行，表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5

105 2 9 3 8 5 7 7

1 2

1 3

1 4

3 5

3 6

3 7

4 8

2 5 1

0 5 2

10 5 3

11 5 4

110 8 2

Sample Output

105

HINT

HINT：

N,M<=100000

暴力自重。。。

题意很好理解，就是树上查找区间第K大，因为不是在线性上的操作，所以建树更新的时候在dfs里更新，查找路径上的第K大，就是区间查找的操作，从x到LCA(x,y)，然后再从LCA(x,y)到y就可以了，因为是点权的操作，所以是去掉lca，然后去掉lca的爸爸，这样就对了。我写的时候写了好久，RE了无数次，最后发现：竟然是我以前LCA的板子不对！！！！(暴风哭泣，气死)，但是我并不知道为什么我的LCA写的为什么不对。。。

代码:

1 //BZOJ 2588 可持久化线段树+LCA  2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
              7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 #include
                
                  12 #include
                 
                   13 #include
                  
                    14 #include
                   
                     15 #include
                     16 #include
                     
                       17 #include
                      
                        18 #include
                       
                         19 #include
                        
                          20 using namespace std; 21 typedef long long ll; 22 23 const double PI=acos(-1.0); 24 const double eps=1e-6; 25 const ll mod=1e9+7; 26 const int inf=0x3f3f3f3f; 27 const int maxn=1e5+10; 28 const int maxm=100+10; 29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 30 #define lson l,m 31 #define rson m+1,r 32 33 int ans,tot,cnt,lca; 34 int n,d,q; 35 int a[maxn],b[maxn],h[maxn],L[maxn<<5],R[maxn<<5]; 36 int to[maxn<<5],head[maxn],Next[maxn<<5];//存图 37 int sum[maxn<<5],root[maxn],dep[maxn]; 38 int fa[maxn][20]; 39 40 void add(int x,int y)//存图 41 { 42 tot++; 43 Next[tot]=head[x]; 44 head[x]=tot; 45 to[tot]=y; 46 } 47 48 int LCA(int x,int y) 49 { 50 if(dep[x]
                         
                          =0;i--){ 55 if(fa[x][i]!=fa[y][i]){ 56 x=fa[x][i]; 57 y=fa[y][i]; 58 } 59 } 60 return fa[x][0]; 61 } 62 63 void update(int pre,int &rt,int l,int r,int k) 64 { 65 rt=++cnt;sum[rt]=sum[pre]+1; 66 L[rt]=L[pre];R[rt]=R[pre]; 67 if(l==r){ 68 return ; 69 } 70 71 int m=(l+r)>>1; 72 if(k<=m) update(L[pre],L[rt],lson,k); 73 else update(R[pre],R[rt],rson,k); 74 } 75 76 int query(int x,int y,int lca,int fa,int l,int r,int k) 77 { 78 if(l==r){ 79 return h[l]; 80 } 81 82 int m=(l+r)>>1; 83 int now=sum[L[x]]+sum[L[y]]-sum[L[lca]]-sum[L[fa]]; 84 if(now>=k) return query(L[x],L[y],L[lca],L[fa],lson,k); 85 else return query(R[x],R[y],R[lca],R[fa],rson,k-now); 86 } 87 88 void dfs(int x,int fath)//按照dfs进行更新 89 { 90 dep[x]=dep[fath]+1; 91 int k=lower_bound(b+1,b+1+d,a[x])-b; 92 h[k]=a[x]; 93 update(root[fath],root[x],1,n,k); 94 for(int i=1;i<=19;i++){ 95 fa[x][i]=fa[fa[x][i-1]][i-1]; 96 } 97 for(int i=head[x];i;i=Next[i]){ 98 if(to[i]!=fath){ 99 fa[to[i]][0]=x;100 dfs(to[i],x);101 }102 }103 }104 105 int main()106 {107 scanf("%d%d",&n,&q);108 for(int i=1;i<=n;i++){109 scanf("%d",&a[i]);110 b[i]=a[i];111 }112 sort(b+1,b+1+n);113 d=unique(b+1,b+1+n)-(b+1);//去重建立权值线段树114 for(int i=1;i

转载于:https://www.cnblogs.com/ZERO-/p/10281726.html

你可能感兴趣的文章