855.md (20237B)
1 Source: https://codeforces.com/blog/entry/54750 2 3 Tutorial is loading... 4 5 **Solution** 6 7 ``` 8 #include<bits/stdc++.h> 9 using namespace std; 10 #define sd(x) scanf("%d",&x) 11 #define slld(x) scanf("%lld",&x) 12 #define ss(x) scanf("%s",x) 13 #define ll long long 14 #define mod 1000000007 15 #define bitcount __builtin_popcountll 16 #define pb push_back 17 #define fi first 18 #define se second 19 #define mp make_pair 20 #define pi pair<int,int> 21 int main() 22 { 23 //freopen("in.txt","r",stdin); 24 //freopen("out.txt","w",stdout); 25 int n,i,j; 26 string s[102]; 27 sd(n); 28 for(i=0;i<n;i++) 29 { 30 cin>>s[i]; 31 for(j=0;j<i;j++) 32 { 33 if(s[i]==s[j]) 34 break; 35 } 36 if(j==i) 37 printf("NO\n"); 38 else 39 printf("YES\n"); 40 } 41 return 0; 42 } 43 ``` 44 45 Tutorial is loading... 46 47 **DP solution 1** 48 49 ``` 50 #include<bits/stdc++.h> 51 using namespace std; 52 #define sd(x) scanf("%d",&x) 53 #define slld(x) scanf("%lld",&x) 54 #define ss(x) scanf("%s",x) 55 #define ll long long 56 #define mod 1000000007 57 #define bitcount __builtin_popcountll 58 #define pb push_back 59 #define fi first 60 #define se second 61 #define mp make_pair 62 #define pi pair<int,int> 63 int a[100005]; 64 ll dp[100005][3]; 65 int main() 66 { 67 //freopen("in.txt","r",stdin); 68 //freopen("out.txt","w",stdout); 69 int n,p,q,r,i; 70 sd(n); 71 sd(p); 72 sd(q); 73 sd(r); 74 for(i=0;i<n;i++) 75 sd(a[i]); 76 dp[0][0]=1ll*p*a[0]; 77 for(i=1;i<n;i++) 78 dp[i][0]=max(dp[i-1][0],1ll*p*a[i]); 79 dp[0][1]=dp[0][0]+1ll*q*a[0]; 80 for(i=1;i<n;i++) 81 dp[i][1]=max(dp[i-1][1],dp[i][0]+1ll*q*a[i]); 82 dp[0][2]=dp[0][1]+1ll*r*a[0]; 83 for(i=1;i<n;i++) 84 dp[i][2]=max(dp[i-1][2],dp[i][1]+1ll*r*a[i]); 85 printf("%lld\n",dp[n-1][2]); 86 return 0; 87 } 88 ``` 89 90 **DP solution 2 with minimum and maximum computation** 91 92 ``` 93 #include<bits/stdc++.h> 94 using namespace std; 95 #define sd(x) scanf("%d",&x) 96 #define slld(x) scanf("%lld",&x) 97 #define ss(x) scanf("%s",x) 98 #define mod 1000000007 99 #define bitcount __builtin_popcountll 100 #define ll long long 101 #define pb push_back 102 #define pi pair<int,int> 103 #define pii pair<pi,int> 104 #define mp make_pair 105 int minleft[100005],minright[100005],maxleft[100005],maxright[100005],a[100005]; 106 int main() 107 { 108 int i,j,k; 109 int n,p,q,r; 110 cin>>n>>p>>q>>r; 111 for(i=1;i<=n;i++) 112 sd(a[i]); 113 minleft[1]=maxleft[1]=a[1]; 114 minright[n]=maxright[n]=a[n]; 115 for(i=2;i<=n;i++) 116 { 117 minleft[i]=min(minleft[i-1],a[i]); 118 maxleft[i]=max(maxleft[i-1],a[i]); 119 } 120 for(i=n-1;i>=1;i--) 121 { 122 minright[i]=min(minright[i+1],a[i]); 123 maxright[i]=max(maxright[i+1],a[i]); 124 } 125 ll ans=-3e18; 126 for(i=1;i<=n;i++) 127 { 128 ll leftval = (p<0) ? 1ll*minleft[i]*p : 1ll*maxleft[i]*p; 129 ll rightval = (r<0) ? 1ll*minright[i]*r : 1ll*maxright[i]*r; 130 ans=max(ans,leftval+rightval+1ll*q*a[i]); 131 } 132 cout<<ans<<endl; 133 return 0; 134 } 135 ``` 136 137 Tutorial is loading... 138 139 **Solution** 140 141 ``` 142 #include<bits/stdc++.h> 143 using namespace std; 144 #define sd(x) scanf("%d",&x) 145 #define slld(x) scanf("%lld",&x) 146 #define ss(x) scanf("%s",x) 147 #define ll long long 148 #define mod 1000000007 149 #define bitcount __builtin_popcountll 150 #define pb push_back 151 #define fi first 152 #define se second 153 #define mp make_pair 154 #define pi pair<int,int> 155 int dp[100005][3][12],x,k,m; 156 int a[3][12],b[3][12]; 157 vector <int> q[100005]; 158 void dfs(int cur,int par) 159 { 160 int i,j=0,l,r,temp; 161 for(i=0;i<q[cur].size();i++) 162 { 163 if(q[cur][i]==par) 164 continue; 165 j=1; 166 dfs(q[cur][i],cur); 167 } 168 if(!j) 169 { 170 dp[cur][0][0]=k-1; 171 dp[cur][1][1]=1; 172 dp[cur][2][0]=m-k; 173 return; 174 } 175 for(i=0;i<3;i++) 176 { 177 for(j=0;j<=x;j++) 178 { 179 a[i][j]=0; 180 b[i][j]=0; 181 } 182 } 183 for(i=0;i<3;i++) 184 a[i][0]=1; 185 for(i=0;i<q[cur].size();i++) 186 { 187 if(q[cur][i]==par) 188 continue; 189 for(j=0;j<3;j++) 190 { 191 for(l=0;l<=x;l++) 192 { 193 for(r=0;r<=x;r++) 194 { 195 if(l+r>x) 196 continue; 197 if(j==0) 198 { 199 temp=dp[q[cur][i]][0][r]+dp[q[cur][i]][1][r]; 200 if(temp>=mod) 201 temp-=mod; 202 temp+=dp[q[cur][i]][2][r]; 203 if(temp>=mod) 204 temp-=mod; 205 b[j][l+r]+=(1ll*a[j][l]*temp)%mod; 206 if(b[j][l+r]>=mod) 207 b[j][l+r]-=mod; 208 } 209 else if(j==1) 210 { 211 b[j][l+r]+=(1ll*a[j][l]*(dp[q[cur][i]][0][r]))%mod; 212 if(b[j][l+r]>=mod) 213 b[j][l+r]-=mod; 214 } 215 else 216 { 217 temp=dp[q[cur][i]][0][r]+dp[q[cur][i]][2][r]; 218 if(temp>=mod) 219 temp-=mod; 220 b[j][l+r]+=(1ll*a[j][l]*temp)%mod; 221 if(b[j][l+r]>=mod) 222 b[j][l+r]-=mod; 223 } 224 } 225 226 } 227 } 228 for(j=0;j<3;j++) 229 { 230 for(l=0;l<=x;l++) 231 { 232 a[j][l]=b[j][l]; 233 b[j][l]=0; 234 } 235 } 236 } 237 for(l=0;l<=x;l++) 238 { 239 dp[cur][0][l]=(1ll*a[0][l]*(k-1))%mod; 240 if(l>=1) 241 dp[cur][1][l]=a[1][l-1]; 242 dp[cur][2][l]=(1ll*a[2][l]*(m-k))%mod; 243 } 244 } 245 int main() 246 { 247 //freopen("in.txt","r",stdin); 248 //freopen("out.txt","w",stdout); 249 int n,i,j,ans; 250 sd(n); 251 sd(m); 252 for(i=1;i<n;i++) 253 { 254 sd(j); 255 sd(k); 256 q[j].pb(k); 257 q[k].pb(j); 258 } 259 sd(k); 260 sd(x); 261 dfs(1,0); 262 ans=0; 263 for(i=0;i<3;i++) 264 { 265 for(j=0;j<=x;j++) 266 { 267 //printf("%d %d %d\n",i,j,dp[1][i][j]); 268 ans+=dp[1][i][j]; 269 if(ans>=mod) 270 ans-=mod; 271 } 272 } 273 printf("%d\n",ans); 274 return 0; 275 } 276 ``` 277 278 Tutorial is loading... 279 280 **Solution** 281 282 ``` 283 #include<bits/stdc++.h> 284 using namespace std; 285 #define sd(x) scanf("%d",&x) 286 #define slld(x) scanf("%lld",&x) 287 #define ss(x) scanf("%s",x) 288 #define mod 1000000007 289 #define bitcount __builtin_popcountll 290 #define ll long long 291 #define pb push_back 292 #define pi pair<int,int> 293 #define pii pair<pi,int> 294 #define mp make_pair 295 vector<int>v[100005],v2[100005]; 296 int inherit[100005],comp[100005],parent[100005][25],height[100005]; 297 int parr[100005]; 298 int findpar(int node) 299 { 300 return parr[node]==node ? node : parr[node]=findpar(parr[node]); 301 } 302 void dfs(int node, int par, int inh, int com) 303 { 304 parent[node][0]=par; 305 inherit[node]=inh; 306 comp[node]=com; 307 height[node]=height[par]+1; 308 for(int i=1;i<=20;i++) 309 { 310 parent[node][i]=parent[parent[node][i-1]][i-1]; 311 } 312 for(int i=0;i<v[node].size();i++) 313 { 314 if(v[node][i]==par) 315 continue; 316 if(v2[node][i]==0) 317 dfs(v[node][i],node,inh+1,com); 318 else 319 dfs(v[node][i],node,inh,com+1); 320 } 321 } 322 int findlca(int u, int v) 323 { 324 if(height[u]>height[v]) 325 swap(u,v); 326 for(int i=20;i>=0;i--) 327 { 328 if(height[parent[v][i]]>=height[u]) 329 { 330 v=parent[v][i]; 331 } 332 } 333 if(u!=v) 334 { 335 for(int i=20;i>=0;i--) 336 { 337 if(parent[u][i]!=parent[v][i]) 338 { 339 u=parent[u][i]; 340 v=parent[v][i]; 341 } 342 } 343 u=parent[u][0]; 344 v=parent[v][0]; 345 } 346 return u; 347 } 348 int main() 349 { 350 int i,j,k; 351 int n,q; 352 sd(n); 353 for(i=1;i<=n;i++) 354 parr[i]=i; 355 for(i=1;i<=n;i++) 356 { 357 sd(j); 358 sd(k); 359 if(j==-1 && k==-1) 360 continue; 361 v[i].pb(j); 362 v[j].pb(i); 363 v2[i].pb(k); 364 v2[j].pb(k); 365 int x=findpar(i); 366 int y=findpar(j); 367 if(x!=y) 368 parr[x]=y; 369 } 370 for(i=1;i<=n;i++) 371 { 372 if(parent[i][0]==0) 373 { 374 dfs(i,i,0,0); 375 } 376 } 377 sd(q); 378 while(q--) 379 { 380 sd(i); 381 sd(j); 382 sd(k); 383 int x=findpar(j); 384 int y=findpar(k); 385 if(x!=y) 386 { 387 printf("NO\n"); 388 continue; 389 } 390 x=findlca(j,k); 391 if(i==1) 392 { 393 if(x!=j || comp[k]-comp[x]!=0 || j==k) 394 { 395 printf("NO\n"); 396 } 397 else 398 printf("YES\n"); 399 } 400 else 401 { 402 if(inherit[k]-inherit[x]!=0 || comp[j]-comp[x]!=0 || x==k) 403 printf("NO\n"); 404 else 405 printf("YES\n"); 406 } 407 } 408 return 0; 409 } 410 ``` 411 412 Tutorial is loading... 413 414 **Solution** 415 416 ``` 417 #include<bits/stdc++.h> 418 using namespace std; 419 #define sd(x) scanf("%lld",&x) 420 #define slld(x) scanf("%lld",&x) 421 #define ss(x) scanf("%s",x) 422 #define ll long long 423 #define mod 1000000007 424 #define bitcount __builtin_popcountll 425 #define pb push_back 426 #define fi first 427 #define se second 428 #define mp make_pair 429 #define pi pair<int,int> 430 ll dp[11][2][1030][70]; 431 ll len[12],a[100]; 432 ll f(ll b,ll in,ll m,ll pos) 433 { 434 if(dp[b][in][m][pos]!=-1) 435 return dp[b][in][m][pos]; 436 if(pos==0) 437 { 438 if(in!=0&&m==0) 439 return dp[b][in][m][pos]=1; 440 else 441 return dp[b][in][m][pos]=0; 442 return dp[b][in][m][pos]; 443 } 444 ll j=0; 445 if(in==0) 446 j+=f(b,0,m,pos-1); 447 else 448 j+=f(b,1,(m^1),pos-1); 449 for(ll i=1;i<b;i++) 450 j+=f(b,1,(m^(1<<i)),pos-1); 451 dp[b][in][m][pos]=j; 452 return j; 453 } 454 int main() 455 { 456 //freopen("in.txt","r",stdin); 457 //freopen("out.txt","w",stdout); 458 ll n,i,j,k,in; 459 ll ans,l,r,m,q,b; 460 k=1e18; 461 memset(dp,-1,sizeof dp); 462 for(i=2;i<=10;i++) 463 { 464 len[i]=1; 465 j=i; 466 while(j<k) 467 { 468 len[i]++; 469 j*=i; 470 } 471 f(i,0,0,len[i]+1); 472 } 473 sd(q); 474 while(q--) 475 { 476 sd(b); 477 sd(l); 478 sd(r); 479 ans=0; 480 l--; 481 if(l) 482 { 483 j=l; 484 i=0; 485 while(j) 486 { 487 a[i]=j%b; 488 j/=b; 489 i++; 490 } 491 m=0; 492 in=0; 493 for(j=i-1;j>=0;j--) 494 { 495 for(k=0;k<a[j];k++) 496 { 497 if(k!=0) 498 in=1; 499 if(in==0) 500 ans-=dp[b][0][m][j]; 501 else 502 ans-=dp[b][1][(m^(1<<k))][j]; 503 } 504 if(in|a[j]) 505 { 506 in=1; 507 m=(m^(1<<a[j])); 508 } 509 } 510 ans-=dp[b][in][m][0]; 511 } 512 j=r; 513 i=0; 514 while(j) 515 { 516 a[i]=j%b; 517 j/=b; 518 i++; 519 } 520 in=0; 521 m=0; 522 for(j=i-1;j>=0;j--) 523 { 524 for(k=0;k<a[j];k++) 525 { 526 if(k!=0) 527 in=1; 528 if(in==0) 529 ans+=dp[b][0][m][j]; 530 else 531 ans+=dp[b][1][(m^(1<<k))][j]; 532 } 533 if(in|a[j]) 534 { 535 in=1; 536 m=(m^(1<<a[j])); 537 } 538 } 539 ans+=dp[b][in][m][0]; 540 printf("%lld\n",ans); 541 } 542 return 0; 543 } 544 ``` 545 546 Tutorial is loading... 547 548 **Solution** 549 550 ``` 551 #include<bits/stdc++.h> 552 using namespace std; 553 #define sd(x) scanf("%d",&x) 554 #define slld(x) scanf("%lld",&x) 555 #define ss(x) scanf("%s",x) 556 #define mod 1000000007 557 #define bitcount __builtin_popcountll 558 #define ll long long 559 #define pb push_back 560 #define fi first 561 #define se second 562 #define pi pair<int,int> 563 #define pii pair<pi,int> 564 #define mp make_pair 565 ll ans[1000]; 566 int upper[1000],lower[1000]; 567 int block; 568 map <int,int> low[1000],up[1000]; 569 map <int,int> vnotup[1000],vnotdown[1000]; 570 int notboth[1000]; 571 int minup[100005],mindown[100005]; 572 void updateup(int i,int l,int r,int val) 573 { 574 if(upper[i]<=val) 575 return; 576 //map<int,int> m; 577 map<int,int> :: iterator it; 578 //m.clear(); 579 for(int j=l;j<=r;j++) 580 { 581 if(minup[j]>val) 582 { 583 if(minup[j]==mod&&mindown[j]==mod&&upper[i]==mod&&lower[i]==mod) 584 { 585 notboth[i]--; 586 //notdown[i]++; 587 vnotdown[i][val]++; 588 //notdownsum[i]+=val; 589 } 590 else if(minup[j]==mod&&upper[i]==mod) 591 { 592 //notup[i]--; 593 int temp=min(lower[i],mindown[j]); 594 vnotup[i][temp]--; 595 if(vnotup[i][temp]==0) 596 vnotup[i].erase(temp); 597 //notupsum[i]-=min(lower[i],mindown[j]); 598 up[i][val]++; 599 low[i][temp]++; 600 ans[i]+=val; 601 ans[i]+=min(lower[i],mindown[j]); 602 } 603 else if(mindown[j]==mod&&lower[i]==mod) 604 { 605 int temp=min(upper[i],minup[j]); 606 vnotdown[i][temp]--; 607 if(vnotdown[i][temp]==0) 608 vnotdown[i].erase(temp); 609 vnotdown[i][val]++; 610 } 611 else 612 { 613 ans[i]+=val-min(upper[i],minup[j]); 614 up[i][min(minup[j],upper[i])]--; 615 up[i][val]++; 616 } 617 minup[j]=val; 618 } 619 } 620 } 621 void updatefullup(int i,int val) 622 { 623 if(val>=upper[i]) 624 return; 625 map <int,int> :: iterator it; 626 int n=up[i].size(); 627 n--; 628 ll sum=0; 629 int len2=0; 630 for(it=vnotup[i].begin();it!=vnotup[i].end();it++) 631 { 632 ans[i]+=1ll*(it->fi)*(it->se)+1ll*(it->se)*val; 633 len2+=it->se; 634 low[i][it->fi]+=it->se; 635 } 636 vnotup[i].clear(); 637 it=vnotdown[i].upper_bound(val); 638 int temp=0; 639 for(it;it!=vnotdown[i].end();it++) 640 { 641 temp+=it->se; 642 } 643 it=vnotdown[i].upper_bound(val); 644 vnotdown[i].erase(it,vnotdown[i].end()); 645 vnotdown[i][val]+=temp+notboth[i]; 646 notboth[i]=0; 647 int len=0; 648 it=up[i].upper_bound(val); 649 for(it;it!=up[i].end();it++) 650 { 651 sum+=1ll*(it->fi)*(it->se); 652 len+=it->se; 653 } 654 it=up[i].upper_bound(val); 655 up[i].erase(it,up[i].end()); 656 ans[i]+=1ll*len*val-sum; 657 up[i][val]+=len+len2; 658 upper[i]=val; 659 } 660 void updatedown(int i,int l,int r,int val) 661 { 662 if(lower[i]<=val) 663 return; 664 //map<int,int> m; 665 map<int,int> :: iterator it; 666 //m.clear(); 667 for(int j=l;j<=r;j++) 668 { 669 if(mindown[j]>val) 670 { 671 if(mindown[j]==mod&&minup[j]==mod&&upper[i]==mod&&lower[i]==mod) 672 { 673 notboth[i]--; 674 //notup[i]++; 675 //notupsum[i]+=val; 676 vnotup[i][val]++; 677 } 678 else if(mindown[j]==mod&&lower[i]==mod) 679 { 680 //notdown[i]--; 681 int temp=min(upper[i],minup[j]); 682 vnotdown[i][temp]--; 683 if(vnotdown[i][temp]==0) 684 vnotdown[i].erase(temp); 685 low[i][val]++; 686 up[i][temp]++; 687 //notdownsum[i]-=min(upper[i],minup[j]); 688 ans[i]+=val; 689 ans[i]+=min(upper[i],minup[j]); 690 } 691 else if(minup[j]==mod&&upper[i]==mod) 692 { 693 int temp=min(lower[i],mindown[j]); 694 vnotup[i][temp]--; 695 if(vnotup[i][temp]==0) 696 vnotup[i].erase(temp); 697 vnotup[i][val]++; 698 } 699 else 700 { 701 ans[i]+=val-min(lower[i],mindown[j]); 702 low[i][min(mindown[j],lower[i])]--; 703 low[i][val]++; 704 } 705 mindown[j]=val; 706 } 707 } 708 } 709 void updatefulldown(int i,int val) 710 { 711 if(val>=lower[i]) 712 return; 713 map <int,int> :: iterator it; 714 int n=low[i].size(); 715 n--; 716 ll sum=0; 717 int len2=0; 718 for(it=vnotdown[i].begin();it!=vnotdown[i].end();it++) 719 { 720 ans[i]+=1ll*(it->fi)*(it->se)+1ll*(it->se)*val; 721 len2+=it->se; 722 up[i][it->fi]+=it->se; 723 } 724 vnotdown[i].clear(); 725 it=vnotup[i].upper_bound(val); 726 int temp=0; 727 for(it;it!=vnotup[i].end();it++) 728 { 729 temp+=it->se; 730 } 731 it=vnotup[i].upper_bound(val); 732 vnotup[i].erase(it,vnotup[i].end()); 733 vnotup[i][val]+=temp+notboth[i]; 734 notboth[i]=0; 735 int len=0; 736 it=low[i].upper_bound(val); 737 for(it;it!=low[i].end();it++) 738 { 739 sum+=1ll*(it->fi)*(it->se); 740 len+=it->se; 741 } 742 it=low[i].upper_bound(val); 743 low[i].erase(it,low[i].end()); 744 ans[i]+=1ll*len*val-sum; 745 low[i][val]+=len+len2; 746 lower[i]=val; 747 } 748 ll query(int i,int l,int r) 749 { 750 ll sum=0; 751 for(int j=l;j<=r;j++) 752 { 753 if(min(upper[i],minup[j])<mod&&min(lower[i],mindown[j])<mod) 754 sum+=min(upper[i],minup[j])+min(lower[i],mindown[j]); 755 } 756 return sum; 757 } 758 ll queryfull(int i) 759 { 760 return ans[i]; 761 } 762 int main() 763 { 764 int i,j,k,q,n,t,l,r,val,block; 765 ll s; 766 n=100000; 767 for(i=0;i<1000;i++) 768 lower[i]=upper[i]=mod; 769 for(i=0;i<=100000;i++) 770 minup[i]=mindown[i]=mod; 771 block=300; 772 for(i=1;i<=n;i++) 773 { 774 j=i/block; 775 notboth[j]++; 776 } 777 sd(q); 778 while(q--) 779 { 780 sd(t); 781 sd(l); 782 sd(r); 783 r--; 784 if(t==1) 785 { 786 sd(val); 787 i=l/block; 788 j=r/block; 789 if(val>0) 790 { 791 if(i==j) 792 updateup(j,l,r,val); 793 else 794 { 795 updateup(i,l,(i+1)*block-1,val); 796 i++; 797 while(i<j) 798 { 799 // updateup(i,i*block,(i+1)*block-1,val); 800 updatefullup(i,val); 801 i++; 802 } 803 updateup(j,j*block,r,val); 804 } 805 } 806 else 807 { 808 if(i==j) 809 updatedown(j,l,r,-val); 810 else 811 { 812 updatedown(i,l,(i+1)*block-1,-val); 813 i++; 814 while(i<j) 815 { 816 // updatedown(i,i*block,(i+1)*block-1,-val); 817 updatefulldown(i,-val); 818 i++; 819 } 820 updatedown(j,j*block,r,-val); 821 } 822 } 823 } 824 else 825 { 826 s=0; 827 i=l/block; 828 j=r/block; 829 if(i==j) 830 s=query(j,l,r); 831 else 832 { 833 s=query(i,l,(i+1)*block-1); 834 i++; 835 while(i<j) 836 { 837 //s+=query(i,i*block,(i+1)*block-1); 838 s+=queryfull(i); 839 i++; 840 } 841 s+=query(j,j*block,r); 842 } 843 printf("%lld\n",s); 844 } 845 } 846 return 0; 847 } 848 ``` 849 850 Tutorial is loading... 851 852 **Solution** 853 854 ``` 855 #include <bits/stdc++.h> 856 857 using namespace std; 858 859 using ll = long long; 860 using ld = long double; 861 using D = double; 862 using uint = unsigned int; 863 template<typename T> 864 using pair2 = pair<T, T>; 865 866 #ifdef WIN32 867 #define LLD "%I64d" 868 #else 869 #define LLD "%lld" 870 #endif 871 872 #define pb push_back 873 #define mp make_pair 874 #define all(x) (x).begin(),(x).end() 875 #define fi first 876 #define se second 877 878 const int maxn = 200005; 879 880 struct tpath 881 { 882 int rep, sz; 883 ll ansmiddle; 884 int edgeleft, edgeright; 885 }; 886 887 int p[maxn], s[maxn]; 888 int sz[maxn], down[maxn], up[maxn], top[maxn]; 889 vector<tpath> path, path2; 890 vector<int> gr[maxn]; 891 ll dp1[maxn], dp2[maxn], ansmiddle[maxn]; 892 int n, m; 893 ll answer; 894 int tin[maxn], tout[maxn]; 895 int timer; 896 897 inline int find(int a) 898 { 899 return (a == p[a] ? a : p[a] = find(p[a])); 900 } 901 902 inline bool isparent(int a, int b) 903 { 904 return tin[a] <= tin[b] && tout[a] >= tin[b]; 905 } 906 907 void unite(int a, int b) 908 { 909 a = find(a); 910 b = find(b); 911 if (a == b) return; 912 if (s[a] > s[b]) swap(a, b); 913 p[a] = b; 914 if (s[a] == s[b]) s[b]++; 915 if (tin[top[a]] < tin[top[b]]) 916 { 917 sz[top[a]] += sz[top[b]]; 918 top[b] = top[a]; 919 } else 920 { 921 sz[top[b]] += sz[top[a]]; 922 } 923 } 924 925 void findpath(int a, int b) 926 { 927 a = top[find(a)]; 928 b = top[find(b)]; 929 // cout << "findpath " << a << ' ' << b << endl; 930 int lastdowna = 0; 931 while (!isparent(a, b)) 932 { 933 path.pb({a, sz[a], ansmiddle[a], lastdowna, n - down[a]}); 934 lastdowna = down[a]; 935 a = top[find(up[a])]; 936 } 937 path2.clear(); 938 int lastdownb = 0; 939 while (a != b) 940 { 941 path2.pb({b, sz[b], ansmiddle[b], n - down[b], lastdownb}); 942 lastdownb = down[b]; 943 b = top[find(up[b])]; 944 } 945 path.pb({a, sz[a], ansmiddle[a], lastdowna, lastdownb}); 946 reverse(all(path2)); 947 for (auto t : path2) path.pb(t); 948 } 949 950 void addedge(int a, int b) 951 { 952 if (find(a) == find(b)) return; 953 path.clear(); 954 findpath(a, b); 955 956 // cout << "addedge " << a << ' ' << b << endl; 957 // for (auto t : path) cout << "(" << t.rep << ' ' << t.sz << ' ' << t.ansmiddle << ' ' << t.edgeleft << ' ' << t.edgeright << ")" << endl; 958 959 // 3 960 ll cnt0 = 1; 961 ll cnt1 = 0; 962 ll cnt2 = 0; 963 for (auto t : path) 964 { 965 answer -= t.sz * cnt2 * 2 + (ll)t.sz * (t.sz - 1) * cnt1 * 2 + (ll)t.sz * (t.sz - 1) * (t.sz - 2); 966 cnt2 += t.sz * cnt1 + (ll)t.sz * (t.sz - 1) * cnt0; 967 cnt1 += t.sz * cnt0; 968 } 969 ll sum = cnt1; 970 answer += ((ll)sum * (sum - 1) * (sum - 2)); 971 972 // cout << "after 3: " << answer << endl; 973 974 // 2 975 cnt1 = 0; 976 for (auto t : path) 977 { 978 answer += cnt1 * (t.edgeleft - cnt1) * t.sz * 2; 979 cnt1 += t.sz; 980 } 981 cnt1 = 0; 982 for (int i = (int)path.size() - 1; i >= 0; i--) 983 { 984 auto &t = path[i]; 985 answer += cnt1 * (t.edgeright - cnt1) * t.sz * 2; 986 cnt1 += t.sz; 987 } 988 989 // cout << "after 2: " << answer << endl; 990 991 // 1 992 cnt1 = 0; 993 cnt2 = 0; 994 for (auto t : path) 995 { 996 answer += cnt2 * t.sz * 2; 997 cnt2 += (n - t.edgeright - t.edgeleft - t.sz) * cnt1; 998 cnt1 += n - t.edgeright - t.edgeleft - t.sz; 999 } 1000 cnt1 = 0; 1001 cnt2 = 0; 1002 for (int i = (int)path.size() - 1; i >= 0; i--) 1003 { 1004 auto &t = path[i]; 1005 answer += cnt2 * t.sz * 2; 1006 cnt2 += (n - t.edgeleft - t.edgeright - t.sz) * cnt1; 1007 cnt1 += n - t.edgeleft - t.edgeright - t.sz; 1008 } 1009 // cout << "after 1 old: " << answer << endl; 1010 ll ttldown1 = 0; 1011 ll ttldown2 = 0; 1012 for (auto t : path) 1013 { 1014 ll curdown = n - t.edgeleft - t.edgeright - t.sz; 1015 ll curdown2 = t.ansmiddle - curdown * (t.edgeleft + t.edgeright) * 2 - (ll)t.edgeleft * t.edgeright * 2; 1016 answer += curdown2 * (sum - t.sz); 1017 ttldown2 = ttldown2 + curdown2 + ttldown1 * curdown * 2; 1018 ttldown1 += curdown; 1019 } 1020 1021 // cout << "after 1: " << answer << endl; 1022 1023 for (int i = 1; i < (int)path.size(); i++) unite(path[i - 1].rep, path[i].rep); 1024 ansmiddle[top[find(path[0].rep)]] = ttldown2; 1025 } 1026 1027 int go(int cur, int pr) 1028 { 1029 down[cur] = 1; 1030 up[cur] = pr; 1031 dp1[cur] = 0; 1032 ansmiddle[cur] = 0; 1033 tin[cur] = timer++; 1034 for (auto t : gr[cur]) if (t != pr) 1035 { 1036 down[cur] += go(t, cur); 1037 answer += (ll)dp1[t] * dp1[cur] * 2; 1038 answer += (ll)dp1[t] * dp2[cur] * 2 + dp2[t] * dp1[cur] * 2; 1039 ansmiddle[cur] += (ll)dp1[t] * dp1[cur] * 2; 1040 answer += dp2[t] * 2; 1041 dp2[cur] += dp2[t]; 1042 dp1[cur] += dp1[t]; 1043 } 1044 ansmiddle[cur] += (ll)(n - down[cur]) * dp1[cur] * 2; 1045 dp2[cur] += dp1[cur]; 1046 dp1[cur] += 1; 1047 tout[cur] = timer - 1; 1048 // cout << "exit " << cur << ' ' << answer << ' ' << dp1[cur] << ' ' << dp2[cur] << endl; 1049 return down[cur]; 1050 } 1051 1052 int main() 1053 { 1054 scanf("%d", &n); 1055 for (int i = 0; i < n - 1; i++) 1056 { 1057 int a, b; 1058 scanf("%d%d", &a, &b); 1059 a--, b--; 1060 gr[a].pb(b); 1061 gr[b].pb(a); 1062 } 1063 go(0, -1); 1064 for (int i = 0; i < n; i++) 1065 { 1066 p[i] = i; 1067 s[i] = 0; 1068 top[i] = i; 1069 sz[i] = 1; 1070 } 1071 printf("%lld\n", answer); 1072 scanf("%d", &m); 1073 for (int i = 0; i < m; i++) 1074 { 1075 int a, b; 1076 scanf("%d%d", &a, &b); 1077 a--, b--; 1078 addedge(a, b); 1079 printf("%lld\n", answer); 1080 } 1081 1082 return 0; 1083 } 1084 ```