家具网站建设公司,黄页88推广多少钱一年,网站新闻专题怎么做,网络培训网站最近学习了LinkCutTree#xff0c;总结一下。 LinkCutTree是一种数据结构#xff08;是Tree Decomposition中的一种#xff09;#xff0c;她维护的一般是无向图#xff08;一个森林#xff09;#xff0c;支持连边、删边、链修改、链查询#xff08;点属于特殊的链总结一下。 LinkCutTree是一种数据结构是Tree Decomposition中的一种她维护的一般是无向图一个森林支持连边、删边、链修改、链查询点属于特殊的链修改可以是单点修改、整链修改查询可以是最值、和等这四种操作。 中心思想是将边分类一类边组成一些连续的链每条链保存在一颗BST中一般是SplayBST中以点到根的距离为关键字左边的点是右边的点的祖先其它一些边连接这些链。LinkCutTree是树链剖分又叫轻重链剖分的动态版本并且更灵活可以证明LinkCutTree的各种操作都是均摊O(logn)的渐进复杂度比树链剖分的O(log^2)还好但是常数巨大所以实测一般时间是树链剖分的1.5~2倍。 上面的“链修改、链查询”指的是链上的点如果要将对象改为边可以为每条边建立一个边点即若存在边(u,v)则新加一个点z代表边将z连接u和vz的点权就是(u,v)的边权非边点的权设为-oo然后对边权的统计就变成了对点权的统计这是LCT中处理边信息的通法之一。 1 #include cstdio2 #include iostream3 #define maxn 100104 using namespace std;5 6 /*7 我的代码风格用数组模拟指针和结构体。8 变量含义9 pnt[u] - path-parent of u in the tree10 pre[u] - the father of u in the Splay11 son[u][0] - the left child of u in the Splay12 son[u][1] - the right child of u in the Splay13 val[u] - the weight of u14 sum[u] - the sum of weight of all the nodes in the subtree of u15 siz[u] - the number of the nodes in the subtree of u16 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][ ndson[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 top0 ) {73 big_push(nd);74 while( pre[nd]!top ) {75 int p pre[nd];76 int nl ndson[p][0];77 if( pre[p]top ) {78 rotate( p, nl );79 } else {80 int pp pre[p];81 int pl pson[pp][0];82 if( nlpl ) {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] ) ndpre[nd];
110 while( pnt[nd] ) {
111 nd pnt[nd];
112 while( pre[nd] ) ndpre[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
