Count on a tree SPOJ - COT （主席树，LCA）-白红宇

Count on a tree SPOJ - COT （主席树，LCA）

阅读量：5217 次

发布时间：2019-06-14

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

You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.

We will ask you to perform the following operation:

u v k : ask for the kth minimum weight on the path from node u to node v

Input

In the first line there are two integers N and M. (N, M <= 100000)

In the second line there are N integers. The ith integer denotes the weight of the ith node.

In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).

In the next M lines, each line contains three integers u v k, which means an operation asking for the kth minimum weight on the path from node u to node v.

Output

For each operation, print its result.

Example

Input:8 5105 2 9 3 8 5 7 71 21 31 43 53 63 74 8 2 5 1 2 5 2 2 5 3 2 5 4 7 8 2

Output:2 8 9 105 7  给出一棵树，每个点都自己的权重，然后给出树上的边，要求从节点 u 到节点 v 路径上的第 k 小的权重的大小。 因为权重可能很大，所以需要离散化。 主席树求区间第 k 小维护的是权值线段树的前缀和，然后通过区间相减得到查询区间的权值线段树 所以树形结构的第 k 小维护的也是权值线段树的前缀和，这里的前缀和表示从第 i 个结点到根的前缀和，比如样例的树是

那么我们用主席树把这八个结点维护成这个样子

那么要得到其中两个点（u，v）之间的树形结构，就可以看成 TREE（u） + TREE（v） - TREE（lca（u，v））- TREE（fa（lca（u，v））），把查询看成四棵树之间的相加相减，然后在求一下lca（u，v）就可以了，这里我比较懒直接用在线的写了

1 /*  2           .  3          ';;;;;.  4         '!;;;;;;!;`  5        '!;|&#@|;;;;!:  6       `;;!&####@|;;;;!:  7      .;;;!&@$$%|!;;;;;;!'.`:::::'.  8      '!;;;;;;;;!$@###&|;;|%!;!$|;;;;|&&;.  9      :!;;;;!$@&%|;;;;;;;;;|!::!!:::;!$%;!$%`    '!%&#########@$!:. 10      ;!;;!!;;;;;|$$&@##$;;;::'''''::;;;;|&|%@$|;;;;;;;;;;;;;;;;!$; 11      ;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;$%` 12     `!!;;;;;;;;;;!|%%|!!;::;;|@##%|$|;;;;;;;;;;;;!|%$#####%;;;%&; 13     :@###&!:;;!!||%%%%%|!;;;;;||;;;;||!$&&@@%;;;;;;;|$$##$;;;%@| 14     ;|::;;;;;;;;;;;;|&&$|;;!$@&$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%. 15    `!!;;;;;;;!!!!;;;;;$@@@&&&&&@$!;!%|;;;;!||!;;;;;!|%%%!;;%@|. 16 %&&$!;;;;;!;;;;;;;;;;;|$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;$##! 17 !%;;;;;;!%!:;;;;;;;;;;!$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;$&: 18 ':|@###%;:;;;;;;;;;;;;!%$&&&&&&@@$!;;;;;;;!!!;;;;;%&!;;|&%. 19  !@|;;;;;;;;;;;;;;;;;;|%|$&&$%&&|;;;;;;;;;;;;!;;;;;!&@@&' 20   .:%#&!;;;;;;;;;;;;;;!%|$$%%&@%;;;;;;;;;;;;;;;;;;;!&@: 21   .%$;;;;;;;;;;;;;;;;;;|$$$$@&|;;;;;;;;;;;;;;;;;;;;%@%. 22     !&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#; 23      `%$!;;;;;;;;;;;$@|;;;;;;;;;;;;;;;;;;;;;;;;!%$@#@|. 24        .|@%!;;;;;;;;;!$&%||;;;;;;;;;;;;;;;;;!%$$$$$@#|. 25            ;&$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|. 26            |##$|!;;;;;;::'':;;;;;;;;;;;;;!%$$$@#@; 27           ;@&|;;;;;;;::'''''':;;;;;;;|$&@###@|` 28         .%##@|;;;;:::''''''''''::;!%&##$' 29       `$##@$$@@&|!!;;;:'''''::::;;;;;|&#%. 30     ;&@##&$%!;;;;;;::''''''''::;!|%$@#@&@@: 31      .%@&$$|;;;;;;;;;;:'''':''''::;;;%@#@@#%. 32     :@##@###@$$$$$|;;:'''':;;!!;;;;;;!$#@@#$;` 33      `%@$$|;;;;;;;;:'''''''::;;;;|%$$|!!&###&' 34      |##&%!;;;;;::''''''''''''::;;;;;;;!$@&:`!' 35     :;!@$|;;;;;;;::''''''''''':;;;;;;;;!%&@$:                !@#$' 36       |##@@&%;;;;;::''''''''':;;;;;;;!%&@#@$%:            '%%!%&; 37       |&%!;;;;;;;%$!:''''''':|%!;;;;;;;;|&@%||`         '%$|!%&; 38       |@%!;;!!;;;||;:'''''':;%$!;;;;!%%%&#&%$&:        .|%;:!&%` 39       !@&%;;;;;;;||;;;:''::;;%$!;;;;;;;|&@%;!$;       `%&%!!$&: 40       '$$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!$##;      !$!;:!$&: 41        |#&|;;;;;;!||;;;;;;;;!%|;;;;!$##$;;;;|%'   `%$|%%;|&$' 42         |&%!;;;;;;|%;;;;;;;;$$;;;;;;|&&|!|%&&;  .:%&$!;;;:!$@! 43         `%#&%!!;;;;||;;;;;!$&|;;;!%%%@&!;;;!!;;;|%!;;%@$!%@! 44         !&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&$;;;|&%;;;%@%` 45        '%|;;;;;;;;!!|$|%&%;;;;;;;;;;|&#&|!!||!!|%$@@|' 46        .!%%&%'`|$;     :|$#%|@#&;%#%. 47 */ 48 #include  49 #include 
       
         50 #include 
        
          51 #include 
         
           52 #include 
          
            53 #include 
           
             54 #include 
            
              55 #include 
             
               56 #include 
              
                57 #include 
               
                 58 #include 
                
                  59 #include 
                 
                   60 #include 
                  
                    61 #include 
                   
                     62 #include 
                    
                      63 #define lowbit(x) x & (-x) 64 #define mes(a, b) memset(a, b, sizeof a) 65 #define fi first 66 #define se second 67 #define pii pair
                     
                       68 #define INOPEN freopen("in.txt", "r", stdin) 69 #define OUTOPEN freopen("out.txt", "w", stdout) 70 71 typedef unsigned long long int ull; 72 typedef long long int ll; 73 const int maxn = 1e5 + 10; 74 const int maxm = 1e5 + 10; 75 const int mod = 1e9 + 7; 76 const ll INF = 1e18 + 100; 77 const int inf = 0x3f3f3f3f; 78 const double pi = acos(-1.0); 79 const double eps = 1e-8; 80 using namespace std; 81 82 int n, m; 83 int cas, tol, T; 84 85 struct Node { 86 int l, r; 87 int sum; 88 } node[maxn * 50]; 89 int a[maxn]; 90 int rt[maxn]; 91 bool vis[maxn]; 92 int deep[maxn]; 93 int fa[maxn][30]; 94 vector
                      
                        vec[maxn]; 95 vector
                       
                         vv; 96 97 void init() { 98 tol = 0; 99 mes(a, 0);100 mes(rt, 0);101 mes(fa, 0);102 mes(vis, 0);103 mes(node, 0);104 mes(deep, 0);105 vv.clear();106 for(int i=1; i<=n; i++)107 vec[i].clear();108 }109 110 int getid(int x) {111 return lower_bound(vv.begin(), vv.end(), x) - vv.begin() + 1;112 }113 114 void lca_dfs(int u, int f, int d) {115 deep[u] = d;116 int len = vec[u].size();117 for(int i=0; i
                        
                         =0; i--) {144 if(fa[u][i] != fa[v][i]) {145 u = fa[u][i];146 v = fa[v][i];147 }148 }149 u = fa[u][0];150 }151 return u;152 }153 154 void hjt_update(int l, int r, int &x, int y, int pos) {155 tol++;156 node[tol] = node[y];157 node[tol].sum++;158 x = tol;159 if(l == r) return ;160 int mid = (l + r) >> 1;161 if(pos <= mid)162 hjt_update(l, mid, node[x].l, node[y].l, pos);163 else164 hjt_update(mid+1, r, node[x].r, node[y].r, pos);165 }166 167 void hjt_build(int u, int f) {168 // printf("%d %d\n", u, f);169 hjt_update(1, n, rt[u], rt[f], getid(a[u]));170 vis[u] = true;171 int len = vec[u].size();172 for(int i=0; i
                         
                          > 1;184 int sum = node[node[x].l].sum + node[node[y].l].sum - node[node[lca].l].sum - node[node[flca].l].sum;185 if(k <= sum)186 return hjt_query(l, mid, node[x].l, node[y].l, node[lca].l, node[flca].l, k);187 else188 return hjt_query(mid+1, r, node[x].r, node[y].r, node[lca].r, node[flca].r, k-sum);189 }190 191 int main() {192 scanf("%d%d", &n, &m);193 init();194 for(int i=1; i<=n; i++) {195 scanf("%d", &a[i]);196 vv.push_back(a[i]);197 }198 sort(vv.begin(), vv.end());199 vv.erase(unique(vv.begin(), vv.end()), vv.end());200 for(int i=1; i

View Code

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/10121047.html

你可能感兴趣的文章