LinkCutTree 總結

最近學習了LinkCutTree，總結一下。

LinkCutTree是一種數據結構（是Tree Decomposition中的一種），她維護的一般是無向圖（一個森林），支持連邊、刪邊、鏈修改、鏈查詢（點屬于特殊的鏈，修改可以是單點修改、整鏈修改，查詢可以是最值、和等）這四種操作。

中心思想是將邊分類，一類邊組成一些連續的鏈，每條鏈保存在一顆BST中（一般是Splay），BST中以點到根的距離為關鍵字（左邊的點是右邊的點的祖先），其它一些邊連接這些鏈。（LinkCutTree是樹鏈剖分（又叫輕重鏈剖分）的動態版本，并且更靈活），可以證明，LinkCutTree的各種操作都是均攤O(logn)的（漸進復雜度比樹鏈剖分的O(log^2)還好，但是常數巨大，所以實測一般時間是樹鏈剖分的1.5~2倍）。

上面的“鏈修改、鏈查詢”指的是鏈上的點，如果要將對象改為邊，可以為每條邊建立一個邊點，即若存在邊(u,v)，則新加一個點z代表邊，將z連接u和v，z的點權就是(u,v)的邊權，非邊點的權設為-oo），然后對邊權的統計就變成了對點權的統計（這是LCT中處理邊信息的通法之一）。

  1 #include <cstdio>
  2 #include <iostream>
  3 #define maxn 10010
  4 using namespace std;
  5 
  6 /*
  7 我的代碼風格：用數組模擬指針和結構體。
  8 變量含義：
  9 pnt[u] - path-parent of u in the tree
 10 pre[u] - the father of u in the Splay
 11 son[u][0] - the left child of u in the Splay
 12 son[u][1] - the right child of u in the Splay
 13 val[u] - the weight of u
 14 sum[u] - the sum of weight of all the nodes in the subtree of u
 15 siz[u] - the number of the nodes in the subtree of u
 16 itg[u] - increasement tag ( the lazy tag )
 17 rtg[u] - rotate tag ( the lazy tag )
 18  */
 19 /*
 20 模板功能：支持刪邊和連邊，支持將一條鏈的點權做一個增量，支持查詢一條鏈的點權和，判斷兩點是否再同一聯通塊中
 21 因為是自己想的一個功能，所以沒有地方交，不保證代碼正確性。(重在理解）
 22 代碼中哪里不懂歡迎回復，代碼丑別噴。
 23 */
 24 namespace L {
 25     int pnt[maxn], pre[maxn], son[maxn][2], val[maxn], 
 26         sum[maxn], siz[maxn], itg[maxn], rtg[maxn];
 27 
 28     void update( int nd ) {
 29         sum[nd] = val[nd] + sum[son[nd][0]] + sum[son[nd][1]];
 30     }
 31     void rotate( int nd, int d ) {
 32         int p = pre[nd];
 33         int s = son[nd][!d];
 34         int ss = son[s][d];
 35 
 36         son[nd][!d] = ss;
 37         son[s][d] = nd;
 38         if( p ) son[p][ nd==son[p][1] ] = s;
 39         else pnt[s] = pnt[nd];
 40 
 41         pre[nd] = s;
 42         pre[s] = p;
 43         pre[ss] = nd;
 44 
 45         update( nd );
 46         update( s );
 47     }
 48     void pushdown( int nd ) {
 49         if( rtg[nd] ) {
 50             int &ls = son[nd][0], &rs = son[nd][1];
 51             swap(ls,rs);
 52             rtg[ls] ^= 1;
 53             rtg[rs] ^= 1;
 54             rtg[nd] = 0;
 55         }
 56         if( itg[nd] ) {
 57             int ls = son[nd][0], rs = son[nd][1];
 58             int delta = itg[nd];
 59             itg[ls] += delta;
 60             itg[rs] += delta;
 61             val[ls] += delta;
 62             val[rs] += delta;
 63             sum[ls] += siz[ls]*delta;
 64             sum[rs] += siz[rs]*delta;
 65             itg[nd] = 0;
 66         }
 67     }
 68     void big_push( int nd ) {
 69         if( pre[nd] ) big_push(pre[nd]);
 70         pushdown(nd);
 71     }
 72     void splay( int nd, int top=0 ) {
 73         big_push(nd);
 74         while( pre[nd]!=top ) {
 75             int p = pre[nd];
 76             int nl = nd==son[p][0];
 77             if( pre[p]==top ) {
 78                 rotate( p, nl );
 79             } else {
 80                 int pp = pre[p];
 81                 int pl = p==son[pp][0];
 82                 if( nl==pl ) {
 83                     rotate( pp, pl );
 84                     rotate( p, nl );
 85                 } else {
 86                     rotate( p, nl );
 87                     rotate( pp, pl );
 88                 }
 89             }
 90         }
 91     }
 92     void access( int nd ) {
 93         int u = nd;
 94         int v = 0;
 95         while( u ) {
 96             splay( u );
 97             int s = son[u][1];
 98             pre[s] = 0;
 99             pnt[s] = u;
100             pre[v] = u;
101             son[u][1] = v;
102             update( u );
103             v = u;
104             u = pnt[u];
105         }
106         splay( nd );
107     }
108     int findroot( int nd ) {
109         while( pre[nd] ) nd=pre[nd];
110         while( pnt[nd] ) {
111             nd = pnt[nd];
112             while( pre[nd] ) nd=pre[nd];
113         }
114         return nd;
115     }
116     void makeroot( int nd ) {
117         access( nd );
118         rtg[nd] ^= 1;
119     }
120     bool sameroot( int u, int v ) {
121         return findroot(u)==findroot(v);
122     }
123     void link( int u, int v  ){
124         makeroot(u);
125         makeroot(v);
126         pnt[u] = v;
127     }
128     void cut( int u, int v ) {
129         makeroot(u);
130         access(v);
131         pnt[u] = 0;
132         pre[u] = 0;
133         son[v][0] = 0;
134         update( v );
135     }
136     void up_val( int u, int v, int delta ) {
137         makeroot(u);
138         access(v);
139         val[v] += delta;
140         sum[v] += siz[v]*delta;
141         itg[v] += delta;
142     }
143     int qu_sum( int u, int v ) {
144         makeroot(u);
145         access(v);
146         return val[v]+sum[son[v][0]];
147     }
148 };
149 /*
150 int main() {
151     L::link(1,2);
152     L::link(2,3);
153     L::link(3,4);
154     L::up_val(1,3,3);
155     L::up_val(2,4,-3);
156     printf( "%d\n", L::qu_sum(1,1) );
157     printf( "%d\n", L::qu_sum(2,2) );
158     printf( "%d\n", L::qu_sum(3,3) );
159     printf( "%d\n", L::qu_sum(4,4) );
160     printf( "%d\n", L::qu_sum(2,3) );
161 }
162 */
163 int main() {
164     L::link(1,2);
165     L::link(2,3);
166     L::link(3,4);
167     L::up_val( 1, 4, 5 );
168     L::cut(2,3);
169     printf( "%d\n", L::qu_sum(1,2) );
170     printf( "%d\n", L::qu_sum(3,4) );
171     printf( "%d\n", L::sameroot(2,3) );
172 }

View Code

推薦學習資料：

楊思雨?《伸展樹的基本操作與應用》

楊哲《QTREE解法的一些研究》

http://blog.csdn.net/d891320478/article/details/9181385

轉載于:https://www.cnblogs.com/idy002/p/4292283.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/273389.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/273389.shtml
英文地址，請注明出處：http://en.pswp.cn/news/273389.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！