1797.md (15573B)
1 Source: https://codeforces.com/blog/entry/114890 2 3 [1797A - Li Hua and Maze](/contest/1797/problem/A "Codeforces Round 864 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (rui_er)** 10 11 ``` 12 //By: OIer rui_er 13 #include <bits/stdc++.h> 14 #define rep(x,y,z) for(int x=(y);x<=(z);x++) 15 #define per(x,y,z) for(int x=(y);x>=(z);x--) 16 #define debug(format...) fprintf(stderr, format) 17 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false) 18 using namespace std; 19 typedef long long ll; 20 21 #define y1 y114514 22 int T, n, m, x1, y1, x2, y2; 23 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;} 24 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} 25 int f(int x, int y) { 26 if((x == 1 || x == n) && (y == 1 || y == m)) return 2; 27 if(x == 1 || x == n || y == 1 || y == m) return 3; 28 return 4; 29 } 30 31 int main() { 32 for(scanf("%d", &T);T;T--) { 33 scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2); 34 printf("%d\n", min(f(x1, y1), f(x2, y2))); 35 } 36 return 0; 37 } 38 ``` 39 40 [1797B - Li Hua and Pattern](/contest/1797/problem/B "Codeforces Round 864 (Div. 2)") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution (rui_er)** 47 48 ``` 49 //By: OIer rui_er 50 #include <bits/stdc++.h> 51 #define rep(x,y,z) for(int x=(y);x<=(z);x++) 52 #define per(x,y,z) for(int x=(y);x>=(z);x--) 53 #define debug(format...) fprintf(stderr, format) 54 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false) 55 using namespace std; 56 typedef long long ll; 57 const int N = 1e3+5; 58 59 int T, n, k, a[N][N]; 60 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;} 61 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} 62 63 int main() { 64 for(scanf("%d", &T);T;T--) { 65 scanf("%d%d", &n, &k); 66 rep(i, 1, n) rep(j, 1, n) scanf("%d", &a[i][j]); 67 int diff = 0; 68 rep(i, 1, n) rep(j, 1, n) if(a[i][j] != a[n+1-i][n+1-j]) ++diff; 69 diff /= 2; 70 if(diff > k) puts("NO"); 71 else { 72 k -= diff; 73 if(n & 1) puts("YES"); 74 else if(k & 1) puts("NO"); 75 else puts("YES"); 76 } 77 } 78 return 0; 79 } 80 ``` 81 82 [1797C - Li Hua and Chess](/contest/1797/problem/C "Codeforces Round 864 (Div. 2)") 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution (rui_er)** 89 90 ``` 91 #include <bits/stdc++.h> 92 using namespace std; 93 94 int T, n, m; 95 96 int ask(int x, int y) { 97 printf("? %d %d\n", x, y); 98 fflush(stdout); 99 scanf("%d", &x); 100 return x; 101 } 102 103 void give(int x, int y) { 104 printf("! %d %d\n", x, y); 105 fflush(stdout); 106 } 107 108 int main() { 109 for(scanf("%d", &T);T;T--) { 110 scanf("%d%d", &n, &m); 111 int T1 = ask(1, 1); 112 if(T1 >= n) { 113 int T2 = ask(1, T1+1); 114 give(T2+1, T1+1); 115 } 116 else if(T1 >= m) { 117 int T2 = ask(T1+1, 1); 118 give(T1+1, T2+1); 119 } 120 else { 121 int T2 = ask(T1+1, 1); 122 int T3 = ask(1, T1+1); 123 if(T2 == T1 && T3 == T1) give(T1+1, T1+1); 124 else if(T3 == T1) give(T1+1, T2+1); 125 else give(T3+1, T1+1); 126 } 127 } 128 return 0; 129 } 130 ``` 131 132 [1797D - Li Hua and Tree](/contest/1797/problem/D "Codeforces Round 864 (Div. 2)") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution (rui_er)** 139 140 ``` 141 //By: Luogu@rui_er(122461) 142 #include <bits/stdc++.h> 143 #define rep(x,y,z) for(ll x=y;x<=z;x++) 144 #define per(x,y,z) for(ll x=y;x>=z;x--) 145 #define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__) 146 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false) 147 using namespace std; 148 typedef long long ll; 149 const ll N = 1e5+5; 150 151 ll n, m, a[N], sz[N], son[N], fa[N], sum[N]; 152 vector<ll> e[N]; 153 set<tuple<ll, ll> > sons[N]; 154 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;} 155 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} 156 void dfs(ll u, ll f) { 157 sz[u] = 1; 158 sum[u] = a[u]; 159 fa[u] = f; 160 for(auto v : e[u]) { 161 if(v == f) continue; 162 dfs(v, u); 163 sz[u] += sz[v]; 164 sum[u] += sum[v]; 165 sons[u].insert(make_tuple(-sz[v], v)); 166 if(sz[v] > sz[son[u]] || sz[v] == sz[son[u]] && v < son[u]) son[u] = v; 167 } 168 } 169 170 int main() { 171 scanf("%lld%lld", &n, &m); 172 rep(i, 1, n) scanf("%lld", &a[i]); 173 rep(i, 1, n-1) { 174 ll u, v; 175 scanf("%lld%lld", &u, &v); 176 e[u].push_back(v); 177 e[v].push_back(u); 178 } 179 dfs(1, 0); 180 while(m --> 0) { 181 ll op, u; 182 scanf("%lld%lld", &op, &u); 183 if(op == 1) printf("%lld\n", sum[u]); 184 else { 185 ll v = son[u]; 186 if(!v) continue; 187 ll p = fa[u]; 188 sz[u] -= sz[v]; 189 sum[u] -= sum[v]; 190 sons[u].erase(make_tuple(-sz[v], v)); 191 son[u] = sons[u].empty() ? 0 : get<1>(*sons[u].begin()); 192 fa[u] = v; 193 sz[v] += sz[u]; 194 sum[v] += sum[u]; 195 sons[v].insert(make_tuple(-sz[u], u)); 196 son[v] = get<1>(*sons[v].begin()); 197 fa[v] = p; 198 sons[p].erase(make_tuple(-sz[v], u)); 199 sons[p].insert(make_tuple(-sz[v], v)); 200 son[p] = get<1>(*sons[p].begin()); 201 } 202 } 203 return 0; 204 } 205 ``` 206 207 [1797E - Li Hua and Array](/contest/1797/problem/E "Codeforces Round 864 (Div. 2)") 208 209 **Tutorial** 210 211 Tutorial is loading... 212 213 **Solution (rui_er)** 214 215 ``` 216 //By: Luogu@rui_er(122461) 217 #include <bits/stdc++.h> 218 #define rep(x,y,z) for(int x=y;x<=z;x++) 219 #define per(x,y,z) for(int x=y;x>=z;x--) 220 #define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__) 221 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false) 222 using namespace std; 223 typedef long long ll; 224 const int N = 1e5 + 5, P = 4e5 + 5, K = 5e6 + 5, W = 5e6; 225 226 int n, m, a[N], tab[K], phi[K], p[P], pcnt, dis[K], fa[K][6]; 227 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;} 228 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} 229 void sieve(int lim) { 230 phi[1] = 1; 231 rep(i, 2, lim) { 232 if(!tab[i]) { 233 p[++pcnt] = i; 234 phi[i] = i - 1; 235 } 236 for(int j=1;j<=pcnt&&1LL*i*p[j]<=lim;j++) { 237 tab[i*p[j]] = 1; 238 if(i % p[j]) phi[i*p[j]] = phi[i] * phi[p[j]]; 239 else { 240 phi[i*p[j]] = phi[i] * p[j]; 241 break; 242 } 243 } 244 } 245 } 246 void initTree(int lim) { 247 dis[1] = 1; 248 rep(j, 0, 5) fa[1][j] = 1; 249 rep(i, 2, lim) { 250 dis[i] = dis[phi[i]] + 1; 251 fa[i][0] = phi[i]; 252 rep(j, 1, 5) fa[i][j] = fa[fa[i][j-1]][j-1]; 253 } 254 } 255 int LCA(int u, int v) { 256 if(dis[u] < dis[v]) swap(u, v); 257 per(i, 5, 0) if(dis[fa[u][i]] >= dis[v]) u = fa[u][i]; 258 if(u == v) return u; 259 per(i, 5, 0) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; 260 return fa[u][0]; 261 } 262 struct Node { 263 int lca, ans, mndis, allrt; 264 }; 265 struct SegTree { 266 Node t[N<<2]; 267 #define lc(u) (u<<1) 268 #define rc(u) (u<<1|1) 269 void pushup(int u, int l, int r) { 270 int mid = (l + r) >> 1; 271 t[u].lca = LCA(t[lc(u)].lca, t[rc(u)].lca); 272 t[u].ans = t[lc(u)].ans + t[rc(u)].ans 273 + (mid - l + 1) * (dis[t[lc(u)].lca] - dis[t[u].lca]) 274 + (r - mid) * (dis[t[rc(u)].lca] - dis[t[u].lca]); 275 t[u].mndis = min(t[lc(u)].mndis, t[rc(u)].mndis); 276 t[u].allrt = t[lc(u)].allrt && t[rc(u)].allrt; 277 } 278 void build(int u, int l, int r) { 279 if(l == r) { 280 t[u].lca = a[l]; 281 t[u].ans = 0; 282 t[u].mndis = dis[a[l]]; 283 t[u].allrt = a[l] == 1; 284 return; 285 } 286 int mid = (l + r) >> 1; 287 build(lc(u), l, mid); 288 build(rc(u), mid+1, r); 289 pushup(u, l, r); 290 } 291 void modify(int u, int l, int r, int ql, int qr) { 292 if(t[u].allrt) return; 293 if(l == r) { 294 t[u].lca = fa[t[u].lca][0]; 295 --t[u].mndis; 296 t[u].allrt = t[u].lca == 1; 297 return; 298 } 299 int mid = (l + r) >> 1; 300 if(ql <= mid) modify(lc(u), l, mid, ql, qr); 301 if(qr > mid) modify(rc(u), mid+1, r, ql, qr); 302 pushup(u, l, r); 303 } 304 int queryLCA(int u, int l, int r, int ql, int qr) { 305 if(ql <= l && r <= qr) return t[u].lca; 306 int mid = (l + r) >> 1; 307 if(qr <= mid) return queryLCA(lc(u), l, mid, ql, qr); 308 if(ql > mid) return queryLCA(rc(u), mid+1, r, ql, qr); 309 int ans = queryLCA(lc(u), l, mid, ql, qr); 310 if(ans == 1) return 1; 311 return LCA(ans, queryLCA(rc(u), mid+1, r, ql, qr)); 312 } 313 int queryAns(int u, int l, int r, int ql, int qr, int lca) { 314 if(ql <= l && r <= qr) { 315 return t[u].ans + (r - l + 1) * (dis[t[u].lca] - dis[lca]); 316 } 317 int mid = (l + r) >> 1, ans = 0; 318 if(ql <= mid) ans += queryAns(lc(u), l, mid, ql, qr, lca); 319 if(qr > mid) ans += queryAns(rc(u), mid+1, r, ql, qr, lca); 320 return ans; 321 } 322 #undef lc 323 #undef rc 324 }sgt; 325 326 int main() { 327 sieve(W); 328 initTree(W); 329 scanf("%d%d", &n, &m); 330 rep(i, 1, n) scanf("%d", &a[i]); 331 sgt.build(1, 1, n); 332 while(m --> 0) { 333 int op, l, r; 334 scanf("%d%d%d", &op, &l, &r); 335 if(op == 1) sgt.modify(1, 1, n, l, r); 336 else { 337 int lca = sgt.queryLCA(1, 1, n, l, r); 338 printf("%d\n", sgt.queryAns(1, 1, n, l, r, lca)); 339 } 340 } 341 return 0; 342 } 343 ``` 344 345 [1797F - Li Hua and Path](/contest/1797/problem/F "Codeforces Round 864 (Div. 2)") 346 347 **Tutorial** 348 349 Tutorial is loading... 350 351 **Solution (Celtic, centroid decomposition)** 352 353 ``` 354 // Celtic 355 #include<bits/stdc++.h> 356 #define N 501001 357 #define MAX 2005 358 using namespace std; 359 typedef long long ll; 360 typedef long double db; 361 const ll inf=1e18,mod=998244353,inv3=(mod+1)/3; 362 inline void read(ll &ret) 363 { 364 ret=0;char c=getchar();bool pd=false; 365 while(!isdigit(c)){pd|=c=='-';c=getchar();} 366 while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();} 367 ret=pd?-ret:ret; 368 return; 369 } 370 ll n,m,x,y,siz[N],son[N],minn=inf,num=0,f[N],sum,root; 371 vector<ll>v[N]; 372 bool vis[N]; 373 inline void find(ll ver,ll fa) 374 { 375 siz[ver]=1; 376 ll maxn=0; 377 for(int i=0;i<v[ver].size();i++) 378 { 379 ll to=v[ver][i]; 380 if(to==fa||vis[to]) 381 continue; 382 find(to,ver); 383 siz[ver]+=siz[to]; 384 maxn=max(maxn,siz[to]); 385 } 386 maxn=max(maxn,num-siz[ver]); 387 if(maxn<minn) 388 { 389 minn=maxn; 390 root=ver; 391 } 392 return; 393 } 394 ll valmx[N],valmn[N],sz[N],now,fat[N]; 395 struct node 396 { 397 ll x,y,ver; 398 }a[N]; 399 inline bool cmp1(node a,node b) 400 { 401 return a.x<b.x; 402 } 403 inline bool cmp2(node a,node b) 404 { 405 return a.y<b.y; 406 } 407 ll cnt; 408 vector<ll>g[N]; 409 inline void dfs(ll ver,ll fa,ll d) 410 { 411 valmx[ver]=max(valmx[fa],ver); 412 valmn[ver]=min(valmn[fa],ver); 413 if(ver!=now) 414 { 415 if(valmx[ver]==ver||valmx[ver]==now) 416 sum++; 417 if(valmn[ver]==ver||valmn[ver]==now) 418 sum++; 419 if(valmx[ver]==ver&&valmn[ver]==now) 420 sum-=2; 421 if(valmx[ver]==now&&valmn[ver]==ver) 422 sum-=2; 423 if(valmn[ver]==ver) 424 f[now]++; 425 if(valmn[ver]==now) 426 f[ver]++; 427 g[d].push_back(ver); 428 a[++cnt]=node{valmx[ver],valmn[ver],ver}; 429 } 430 sz[ver]=1; 431 fat[ver]=d; 432 // cout<<"dfs"<<ver<<" "<<fa<<" "<<d<<endl; 433 for(int i=0;i<v[ver].size();i++) 434 { 435 ll to=v[ver][i]; 436 if(to==fa||vis[to]) 437 continue; 438 if(ver==now) 439 dfs(to,ver,to); 440 else 441 dfs(to,ver,d); 442 sz[ver]+=sz[to]; 443 } 444 return; 445 } 446 ll tree[N]; 447 inline void update(ll pos,ll num) 448 { 449 pos++; 450 while(pos<N) 451 { 452 tree[pos]+=num; 453 pos+=pos&-pos; 454 } 455 return; 456 } 457 inline ll query(ll pos) 458 { 459 pos++; 460 ll ret=0; 461 while(pos) 462 { 463 ret+=tree[pos]; 464 pos-=pos&-pos; 465 } 466 return ret; 467 } 468 inline void calc() 469 { 470 sort(a+1,a+cnt+1,cmp1); 471 for(int i=1;i<=cnt;i++) 472 { 473 ll j=i; 474 for(;j<=cnt&&a[j].x==a[i].x;j++); 475 j--; 476 for(int k=i;k<=j;k++) 477 { 478 if(a[k].x==a[k].ver) 479 sum+=i-1,sum-=2*query(a[k].y)/*,cout<<"del "<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/; 480 } 481 for(int k=i;k<=j;k++) 482 { 483 if(a[k].y==a[k].ver) 484 update(a[k].y,1); 485 } 486 i=j; 487 } 488 for(int i=1;i<=cnt;i++) 489 { 490 ll j=i; 491 for(;j<=cnt&&a[j].x==a[i].x;j++); 492 j--; 493 for(int k=i;k<=j;k++) 494 { 495 if(a[k].y==a[k].ver) 496 update(a[k].y,-1); 497 } 498 i=j; 499 } 500 sort(a+1,a+cnt+1,cmp2); 501 for(int i=cnt;i;i--) 502 { 503 ll j=i; 504 for(;j&&a[j].y==a[i].y;j--); 505 j++; 506 for(int k=j;k<=i;k++) 507 { 508 if(a[k].y==a[k].ver) 509 sum+=cnt-i; 510 } 511 i=j; 512 } 513 ll tmp=0; 514 for(int i=1;i<=cnt;i++) 515 { 516 ll j=i; 517 for(;j<=cnt&&a[j].y==a[i].y;j++); 518 j--; 519 for(int k=i;k<=j;k++) 520 f[a[k].ver]+=tmp; 521 for(int k=i;k<=j;k++) 522 if(a[k].ver==a[k].y) 523 tmp++; 524 i=j; 525 } 526 return; 527 } 528 inline void decalc() 529 { 530 sort(a+1,a+cnt+1,cmp1); 531 for(int i=1;i<=cnt;i++) 532 { 533 ll j=i; 534 for(;j<=cnt&&a[j].x==a[i].x;j++); 535 j--; 536 for(int k=i;k<=j;k++) 537 { 538 if(a[k].x==a[k].ver) 539 sum-=i-1,sum+=2*query(a[k].y)/*,cout<<"back"<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/; 540 } 541 for(int k=i;k<=j;k++) 542 { 543 if(a[k].y==a[k].ver) 544 update(a[k].y,1); 545 } 546 i=j; 547 } 548 for(int i=1;i<=cnt;i++) 549 { 550 ll j=i; 551 for(;j<=cnt&&a[j].x==a[i].x;j++); 552 j--; 553 for(int k=i;k<=j;k++) 554 { 555 if(a[k].y==a[k].ver) 556 update(a[k].y,-1); 557 } 558 i=j; 559 } 560 sort(a+1,a+cnt+1,cmp2); 561 for(int i=cnt;i;i--) 562 { 563 ll j=i; 564 for(;j&&a[j].y==a[i].y;j--); 565 j++; 566 for(int k=j;k<=i;k++) 567 { 568 if(a[k].y==a[k].ver) 569 sum-=cnt-i; 570 } 571 i=j; 572 } 573 ll tmp=0; 574 for(int i=1;i<=cnt;i++) 575 { 576 ll j=i; 577 for(;j<=cnt&&a[j].y==a[i].y;j++); 578 j--; 579 for(int k=i;k<=j;k++) 580 f[a[k].ver]-=tmp; 581 for(int k=i;k<=j;k++) 582 if(a[k].ver==a[k].y) 583 tmp++; 584 i=j; 585 } 586 return; 587 } 588 inline void divide(ll ver) 589 { 590 vis[ver]=true; 591 now=ver; 592 cnt=0; 593 valmn[0]=inf; 594 dfs(ver,0,0); 595 // cout<<"??"<<ver<<" "<<sum<<endl; 596 /* cout<<ver<<endl; 597 for(int i=1;i<=cnt;i++) 598 cout<<a[i].x<<" "<<a[i].y<<endl;*/ 599 calc(); 600 // cout<<ver<<" "<<cnt<<endl; 601 for(int i=0;i<v[ver].size();i++) 602 { 603 ll to=v[ver][i]; 604 if(vis[to]) 605 continue; 606 cnt=0; 607 for(auto x:g[to]) 608 a[++cnt]=node{valmx[x],valmn[x],x}/*,cout<<ver<<" "<<to<<" "<<x<<endl*/; 609 g[to].clear(); 610 // cout<<ver<<" "<<to<<" "<<cnt<<endl; 611 decalc(); 612 } 613 // cout<<"result::"<<ver<<" "<<sum<<endl; 614 for(int i=0;i<v[ver].size();i++) 615 { 616 ll to=v[ver][i]; 617 if(vis[to]) 618 continue; 619 num=siz[to]; 620 minn=inf; 621 find(to,ver); 622 // cout<<ver<<" "<<to<<" "<<root<<endl; 623 divide(root); 624 } 625 return; 626 } 627 signed main() 628 { 629 read(n); 630 for(int i=1;i<n;i++) 631 { 632 read(x); 633 read(y); 634 v[x].push_back(y); 635 v[y].push_back(x); 636 } 637 num=n; 638 find(1,0); 639 divide(root); 640 printf("%lld\n",sum); 641 /* for(int i=1;i<=n;i++) 642 cout<<f[i]<<" "; 643 cout<<endl;*/ 644 read(m); 645 for(int i=1;i<=m;i++) 646 { 647 ll x; 648 read(x); 649 n++; 650 f[n]=f[x]+1; 651 sum+=(n-1)-f[n]; 652 printf("%lld\n",sum); 653 } 654 exit(0); 655 } 656 ``` 657 658 **Solution (rui_er, reconstruction trees)** 659 660 ``` 661 //By: OIer rui_er 662 #include <bits/stdc++.h> 663 #define rep(x,y,z) for(ll x=(y);x<=(z);x++) 664 #define per(x,y,z) for(ll x=(y);x>=(z);x--) 665 #define debug(format...) fprintf(stderr, format) 666 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false) 667 using namespace std; 668 typedef long long ll; 669 const ll N = 4e5+5; 670 671 ll n, m, k, faMx[N], faMn[N], disMx[N], disMn[N], dfn[N], sz[N], tms; 672 ll A, B, C, ans; 673 vector<ll> eMx[N], eMn[N], reMx[N], reMn[N]; 674 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;} 675 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} 676 struct Dsu { 677 ll fa[N]; 678 void init(ll x) {rep(i, 1, x) fa[i] = i;} 679 ll find(ll x) {return x == fa[x] ? x : fa[x] = find(fa[x]);} 680 bool merge(ll x, ll y) { 681 ll u = find(x), v = find(y); 682 if(u == v) return 0; 683 fa[u] = v; 684 return 1; 685 } 686 }dsu; 687 struct BIT { 688 ll c[N], sz; 689 void init(ll x) {sz = x; rep(i, 1, x) c[i] = 0;} 690 ll lowbit(ll x) {return x & (-x);} 691 void add(ll x, ll k) {for(; x <= sz; x += lowbit(x)) c[x] += k;} 692 ll ask(ll x) {ll k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;} 693 ll Ask(ll x, ll y) {return ask(y) - ask(x - 1);} 694 }bit; 695 void dfs1(ll u) { 696 dfn[u] = ++tms; 697 sz[u] = 1; 698 disMx[u] = disMx[faMx[u]] + 1; 699 B += disMx[u] - 1; 700 for(ll v : reMx[u]) { 701 dfs1(v); 702 sz[u] += sz[v]; 703 } 704 } 705 void dfs2(ll u) { 706 disMn[u] = disMn[faMn[u]] + 1; 707 A += disMn[u] - 1; 708 C += bit.Ask(dfn[u], dfn[u] + sz[u] - 1); 709 bit.add(dfn[u], 1); 710 for(ll v : reMn[u]) dfs2(v); 711 bit.add(dfn[u], -1); 712 } 713 714 int main() { 715 scanf("%lld", &n); 716 rep(i, 1, n-1) { 717 ll u, v; 718 scanf("%lld%lld", &u, &v); 719 if(u < v) swap(u, v); 720 eMx[u].push_back(v); 721 eMn[v].push_back(u); 722 } 723 dsu.init(n); 724 rep(i, 1, n) { 725 for(ll j : eMx[i]) { 726 j = dsu.find(j); 727 dsu.merge(j, i); 728 faMx[j] = i; 729 reMx[i].push_back(j); 730 } 731 } 732 dsu.init(n); 733 per(i, n, 1) { 734 for(ll j : eMn[i]) { 735 j = dsu.find(j); 736 dsu.merge(j, i); 737 faMn[j] = i; 738 reMn[i].push_back(j); 739 } 740 } 741 bit.init(n); 742 dfs1(n); 743 dfs2(1); 744 ans = A + B - 2 * C; 745 // printf("%lld + %lld - 2 * %lld = %lld\n", A, B, C, ans); 746 printf("%lld\n", ans); 747 for(scanf("%lld", &m); m; m--) { 748 scanf("%lld", &k); 749 disMn[++n] = disMn[k] + 1; 750 ans += n - disMn[n]; 751 printf("%lld\n", ans); 752 } 753 return 0; 754 } 755 ```