小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。
例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。
现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。
1 #include<iostream> 2 #include<stdio.h> 3 #include<vector> 4 #include<map> 5 #include<algorithm> 6 #define maxn 300030 7 using namespace std; 8 struct node{ 9 int l; 10 int r; 11 int rmax; 12 int tag; 13 node* left; 14 node* right; 15 int val; 16 }e1[maxn *5]; 17 int ttop = -1; 18 int fw[maxn]; 19 inline void pushdown(node* x){ 20 if(!x->left || !x->right){ 21 return; 22 } 23 if(!x->tag){ 24 return; 25 } 26 x->left->val += x->tag * (x->left->r - x->left->l +1); 27 x->left->tag += x->tag; 28 x->right->val += x->tag * (x->right->r - x->right->l + 1); 29 x->right->tag += x->tag; 30 x->tag = 0; 31 } 32 inline void update(node* cur){ 33 cur->val = cur->left->val +cur->right->val; 34 if(cur->right->rmax == cur->right->r - cur->right->l + 1){ 35 cur->rmax = cur->left->rmax + cur->right->rmax; 36 } 37 else{ 38 cur->rmax = cur->right->rmax; 39 } 40 } 41 node* root; 42 node* build(int l,int r){ 43 node* cur = &e1[++ttop]; 44 cur->l = l; 45 cur->r = r; 46 if(l == r){ 47 cur->val = 0; 48 return cur; 49 } 50 int mid = (l+r) >>1; 51 cur->left = build(l,mid); 52 cur->right = build(mid+1,r); 53 update(cur); 54 return cur; 55 } 56 int find(node* cur,int l,int r){ 57 pushdown(cur); 58 if(cur->l == l && cur->r == r){ 59 return cur->rmax; 60 } 61 int mid = (cur->l + cur->r) >>1; 62 if(r <= mid){ 63 return find(cur->left,l,r); 64 } 65 else if( l > mid){ 66 return find(cur->right,l,r); 67 } 68 else{ 69 int lxl1 = find(cur->left,l,mid); 70 int lxl2 = find(cur->right,mid+1,r); 71 if(lxl2 == r - mid){ 72 return lxl1+lxl2; 73 } 74 else{ 75 return lxl2; 76 } 77 } 78 } 79 int get(node* cur,int pos){ 80 pushdown(cur); 81 if(cur->l == cur->r){ 82 return cur->val; 83 } 84 int mid = (cur->l + cur->r) >>1; 85 if(pos <= mid){ 86 return get(cur->left,pos); 87 } 88 else{ 89 return get(cur->right,pos); 90 } 91 } 92 void modify2(node* cur,int pos){ 93 pushdown(cur); 94 if(cur->l == cur->r){ 95 cur->rmax = 1; 96 return; 97 } 98 int mid = (cur->l + cur->r) >>1; 99 if(pos <= mid){ 100 modify2(cur->left,pos); 101 } 102 else{ 103 modify2(cur->right,pos); 104 } 105 update(cur); 106 } 107 void modify1(node* cur,int pos){ 108 pushdown(cur); 109 if(cur->l == cur->r){ 110 cur->val = 1; 111 return; 112 } 113 int mid = (cur->l + cur->r) >>1; 114 if(pos <= mid){ 115 modify1(cur->left,pos); 116 } 117 else{ 118 modify1(cur->right,pos); 119 } 120 update(cur); 121 } 122 void modify(node* cur,int l,int r,int va){ 123 pushdown(cur); 124 if(cur->l == l && cur->r == r){ 125 cur->val += va * (cur->r - cur->l + 1); 126 cur->tag += va; 127 return; 128 } 129 int mid = (cur->l + cur->r) >>1; 130 if(r <= mid){ 131 modify(cur->left,l,r,va); 132 } 133 else if(l > mid){ 134 modify(cur->right,l,r,va); 135 } 136 else{ 137 modify(cur->left,l,mid,va); 138 modify(cur->right,mid+1,r,va); 139 } 140 update(cur); 141 } 142 struct edge { 143 int np; 144 int next; 145 } e[maxn]; 146 int top2 =1; 147 int head[maxn]; 148 inline void add(int x,int y) { 149 e[++top2] = (edge) { 150 y,head[x] 151 }; 152 head[x] = top2; 153 e[++top2] = (edge) { 154 x,head[y] 155 }; 156 head[y] = top2; 157 } 158 159 int fa[maxn]; 160 int deep[maxn]; 161 int size[maxn]; 162 int son[maxn]; 163 int top[maxn]; 164 int w[maxn]; 165 int mp[maxn]; 166 bool mark[maxn]; 167 int hroot; 168 void dfs1(int x) { 169 int sizesum =1; 170 int sizetmp = 0; 171 int cur; 172 for(int i = head[x]; i; i = e[i].next) { 173 cur = e[i].np; 174 if(!deep[cur]) { 175 deep[cur] = deep[x] + 1; 176 fa[cur] = x; 177 dfs1(cur); 178 sizesum += size[cur]; 179 if(size[cur] > sizetmp) { 180 sizetmp = size[cur]; 181 son[x] = cur; 182 } 183 } 184 } 185 size[x] = sizesum; 186 } 187 int index = 0; 188 inline void initd2() { 189 deep[hroot] = 1; 190 top[hroot] = hroot; 191 w[hroot] = ++index; 192 fa[hroot] = 0; 193 } 194 void dfs2(int x,int top1) { 195 if(son[x] != 0) { 196 top[son[x]] = top1; 197 w[son[x]] = ++index; 198 dfs2(son[x],top1); 199 } 200 int cur; 201 for(int i =head[x]; i; i = e[i].next) { 202 cur = e[i].np; 203 if(cur != son[x] && cur != fa[x]) { 204 top[cur] = cur; 205 w[cur] = ++index; 206 dfs2(cur,cur); 207 } 208 } 209 } 210 void update1(int u){ 211 if(u == 7){ 212 int hjah = 0; 213 } 214 int nowadd = get(root,w[u]); 215 int fu; 216 modify(root,w[u],w[u],-nowadd); 217 do{ 218 fu = top[u]; 219 int len = 0; 220 if(w[fu]+1 <= w[u]){ 221 len = find(root,w[fu]+1,w[u]); 222 } 223 if(len == w[u] - w[fu]){ 224 modify(root,w[fu],w[u],nowadd); 225 if(find(root,w[fu],w[fu])){ 226 u = fa[fu]; 227 } 228 else{ 229 break; 230 } 231 } 232 else{ 233 int idlast = w[u] - len; 234 modify(root,idlast,w[u],nowadd); 235 break; 236 } 237 }while(u != 0); 238 } 239 struct line{ 240 int l; 241 int r; 242 //int id; 243 }; 244 struct qu{ 245 line now; 246 int type; 247 }zqq[maxn]; 248 int n; 249 int a,b,c; 250 int q; 251 int op; 252 int get_r_id(int u){ 253 int fu = top[u]; 254 do{ 255 int len = 0; 256 if(w[fu] + 1 <= w[u]){ 257 len = find(root,w[fu]+1,w[u]); 258 } 259 if(len == w[u]-w[fu]){ 260 if(find(root,w[fu],w[fu])){ 261 u = fa[fu]; 262 } 263 else{ 264 return w[fu]; 265 } 266 } 267 else{ 268 return w[u] - len; 269 } 270 }while( u != 0); 271 if(u == hroot){ 272 return w[hroot]; 273 } 274 } 275 int pre[maxn]; 276 int mark2[maxn]; 277 int get_pre(int a){ 278 int tmp = a; 279 while(a != pre[a]){ 280 a = pre[a]; 281 } 282 while(tmp != pre[tmp]){ 283 pre[tmp] = a; 284 tmp = pre[tmp]; 285 } 286 return a; 287 } 288 void un(int a,int b){ 289 int haha1 = get_pre(a); 290 int haha2 = get_pre(b); 291 pre[haha1] = haha2; 292 } 293 int main(){ 294 freopen("333.in","r",stdin); 295 freopen("my.out","w",stdout); 296 scanf("%d %d",&n,&q); 297 bool flag = true; 298 for(int i =0;i<=n;i++){ 299 pre[i] = i; 300 } 301 for(int i =1;i<=q;i++){ 302 a = getchar(); 303 while(a == ‘ ‘|| a == ‘\n‘){ 304 a = getchar(); 305 } 306 scanf("%d %d",&b,&c); 307 if(a == ‘A‘){ 308 if(flag){ 309 flag = false; 310 hroot = b; 311 } 312 zqq[i].now = (line){b,c}; 313 add(b,c); 314 un(b,c); 315 zqq[i].type = 1; 316 } 317 else{ 318 zqq[i].now = (line){b,c}; 319 zqq[i].type = 0; 320 } 321 } 322 int p_root = get_pre(hroot); 323 for(int i =1;i<=n;i++){ 324 int cyz = get_pre(i); 325 if(cyz != p_root && !mark2[cyz]){ 326 mark2[cyz] = 1; 327 add(cyz,hroot); 328 } 329 } 330 initd2(); 331 dfs1(hroot); 332 dfs2(hroot,hroot); 333 root = build(1,index); 334 for(int i =1;i<=q;i++){ 335 int tmp1 = zqq[i].now.l; 336 int tmp2 = zqq[i].now.r; 337 if(!mark[tmp1]){ 338 modify1(root,w[tmp1]); 339 mark[tmp1] = 1; 340 } 341 if(!mark[tmp2]){ 342 modify1(root,w[tmp2]); 343 mark[tmp2] = 1; 344 } 345 if(i == 1){ 346 modify2(root,w[zqq[i].now.r]); 347 update1(zqq[i].now.r); 348 continue; 349 } 350 if(zqq[i].type == 1){ 351 tmp1 = zqq[i].now.l; 352 tmp2 = zqq[i].now.r; 353 mark[tmp1] = mark[tmp2] = 1; 354 if(fa[tmp1] == tmp2){ 355 modify2(root,w[tmp1]); 356 update1(tmp1); 357 } 358 else{ 359 modify2(root,w[tmp2]); 360 update1(tmp2); 361 } 362 } 363 else{ 364 tmp1 = zqq[i].now.l; 365 tmp2 = zqq[i].now.r; 366 if(tmp1 == 7 && tmp2 == 8){ 367 int hahas = 0; 368 } 369 int nowrootid; 370 if(fa[tmp1] == tmp2){ 371 nowrootid = get_r_id(tmp2); 372 int sizetot = get(root,nowrootid); 373 int sizea = get(root,w[tmp1]); 374 int sizeb = sizetot - sizea; 375 printf("%d\n",sizea * sizeb); 376 } 377 else{ 378 nowrootid = get_r_id(tmp1); 379 int sizetot = get(root,nowrootid); 380 int sizea = get(root,w[tmp2]); 381 int sizeb = sizetot - sizea; 382 printf("%d\n",sizea * sizeb); 383 } 384 } 385 } 386 }
首先离线链剖（把最后的树的形态确定。。主要如果有多个互不相交的树要自己补全为一棵树）
唉。。太丑原谅。。。毕竟考试的时候边界挂了。。。线段树维护每个节点的子树的size。。每次加入一条边就维护下连通性（线段树上把这条边改为1）。。我是用线段树维护每个区间从右开始的连续为1的最大的长度。。直接get_r_id求出当前的这个点所在的联通块的root。。然后在连边的时候更新你连上之后并入新联通块之后新联通块里从这个点开始到联通块root这条链上的每个点的子树size。。（线段树区间修改）。查询答案就先找到这条边的father和儿子的关系。然后get_r_id找到father所在联通块的顶点。得到这个联通块的siz然后再找到son的子树的大小。。答案就是（当前联通块大小-son子树大小）*son子树大小。。。
虽然有可以用并茶几维护联通块的
原文：http://www.cnblogs.com/andyoier/p/5293331.html