codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1527.md (27182B)


      1 Source: https://codeforces.com/blog/entry/90939
      2 
      3 [1527A - And Then There Were K](/contest/1527/problem/A "Codeforces Round 721 (Div. 2)")
      4 
      5 Author: [loud_mouth](/profile/loud_mouth "Expert loud_mouth")  
      6  Idea: [Bignubie](/profile/Bignubie "Candidate Master Bignubie")
      7 
      8 **Editorial**
      9 
     10 Tutorial is loading...
     11 
     12 **Solution (Loud_mouth)** 
     13 
     14 ```
     15 #include<bits/stdc++.h>
     16 using namespace std;
     17 #define ll long long
     18 
     19 int main()
     20 {
     21 	int t;
     22 	cin>>t;
     23 	while(t--)
     24 	{
     25 		int n;
     26 		cin>>n;
     27 		int last=0;
     28 		for(int i=0; i<30; ++i)
     29 		{
     30 			if(((n>>i)&1) == 1)
     31 			{
     32 				last=i;
     33 			}
     34 		}
     35 		cout<<(1<<last)-1<<"\n";
     36 	}
     37 	return 0;	
     38 }
     39 ```
     40 
     41 **Solution (the_nightmare)** 
     42 
     43 ```
     44 #include<bits/stdc++.h>
     45 #include <ext/pb_ds/assoc_container.hpp>
     46 #include <ext/pb_ds/tree_policy.hpp>
     47 #define ll          long long
     48 #define pb          push_back
     49 #define ppb         pop_back
     50 #define endl        '\n'
     51 #define mii         map<ll,ll>
     52 #define msi         map<string,ll>
     53 #define mis         map<ll, string>
     54 #define rep(i,a,b)    for(ll i=a;i<b;i++)
     55 #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
     56 #define trav(a, x)  for(auto& a : x)
     57 #define pii         pair<ll,ll>
     58 #define vi          vector<ll>
     59 #define vii         vector<pair<ll, ll>>
     60 #define vs          vector<string>
     61 #define all(a)      (a).begin(),(a).end()
     62 #define F           first
     63 #define S           second
     64 #define sz(x)       (ll)x.size()
     65 #define hell        1000000007
     66 #define lbnd        lower_bound
     67 #define ubnd        upper_bound
     68 #define DEBUG       cerr<<"/n>>>I'm Here<<</n"<<endl;
     69 #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
     70 #define what_is(x)  cerr << #x << " is " << x << endl;
     71 #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
     72 #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     73 using namespace __gnu_pbds;
     74 using namespace std;
     75 #define PI 3.141592653589793
     76 #define N  200005
     77 void solve()
     78 {
     79     ll n;
     80     cin >> n;
     81     ll cnt=0;
     82     while(n!=0){
     83         cnt++;
     84         n=n/2;
     85     }
     86     cout << (1<<(cnt-1))-1 << endl;
     87 }
     88 int main()
     89 {
     90     #ifndef ONLINE_JUDGE
     91     freopen ("input.txt","r",stdin);
     92     #endif
     93     ll int TEST=1;
     94     cin >> TEST;
     95     //init();
     96     while(TEST--)
     97     {
     98         solve();
     99     }
    100 }
    101 ```
    102 
    103 [1527B1 - Palindrome Game (easy version)](/contest/1527/problem/B1 "Codeforces Round 721 (Div. 2)")
    104 
    105 Author: [DenOMINATOR](/profile/DenOMINATOR "Master DenOMINATOR")  
    106  Idea: [shikhar7s](/profile/shikhar7s "Master shikhar7s")
    107 
    108 **Editorial**
    109 
    110 Tutorial is loading...
    111 
    112 **Solution (DenOMINATOR)** 
    113 
    114 ```
    115 #include<bits/stdc++.h>
    116 using namespace std;
    117 
    118 void solve(){
    119 	int n;
    120 	cin >> n;
    121 	string s;
    122 	cin >> s;
    123 	bool is_palindrome=1;
    124 	int cnt_0 = 0;
    125 	for(int i=0;i<n;i++){
    126 		cnt_0 += s[i]=='0';
    127 	}
    128 	if(cnt_0 == 1){
    129 		cout << "BOB\n";
    130 		return;
    131 	}
    132 	if(cnt_0%2){
    133 		cout << "ALICE\n";
    134 		return;
    135 	}
    136 	cout << "BOB\n";
    137 	return;
    138 }
    139 
    140 signed main()
    141 {
    142 	int t;
    143 	cin >> t;
    144 	while(t--){
    145 		solve();
    146 	}
    147     return 0;
    148 }
    149 ```
    150 
    151 **Solution (shikhar7s)** 
    152 
    153 ```
    154 #include<bits/stdc++.h>
    155 using namespace std;
    156 #define int long long int
    157 #define mp(a,b) make_pair(a,b)
    158 #define vi vector<int>
    159 #define mii map<int,int>
    160 #define mpi map<pair<int,int>,int>
    161 #define vp vector<pair<int,int> >
    162 #define pb(a) push_back(a)
    163 #define fr(i,n) for(i=0;i<n;i++)
    164 #define rep(i,a,n) for(i=a;i<n;i++)
    165 #define F first
    166 #define S second
    167 #define endl "\n"
    168 #define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    169 #define mod 1000000007
    170 #define dom 998244353
    171 #define sl(a) (int)a.length()
    172 #define sz(a) (int)a.size()
    173 #define all(a) a.begin(),a.end()
    174 #define pii pair<int,int> 
    175 #define mini 2000000000000000000
    176 #define time_taken 1.0 * clock() / CLOCKS_PER_SEC
    177 //const long double pi = acos(-1);
    178 //mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    179 //primes for hashing 937, 1013
    180 template<typename T, typename U> static inline void amin(T &x, U y) 
    181 { 
    182     if (y < x) 
    183         x = y; 
    184 }
    185 template<typename T, typename U> static inline void amax(T &x, U y) 
    186 { 
    187     if (x < y) 
    188         x = y; 
    189 }
    190 void shikhar7s(int cas)
    191 {
    192     int n,i;
    193     cin>>n;
    194     string s;
    195     cin>>s;
    196     int f=1,z=0;
    197     fr(i,n)
    198     {
    199         if(s[i]=='0')
    200             z++;
    201     }
    202     int x=0;
    203     fr(i,n/2)
    204     {
    205         if(s[i]!=s[n-1-i])
    206         {
    207             f=0;
    208             x++;
    209         }
    210     }
    211     if(f)
    212     {
    213         if(z==1||z%2==0)
    214             cout<<"BOB"<<endl;
    215         else
    216             cout<<"ALICE"<<endl;
    217     }
    218     else
    219     {
    220         if(x==1&&z==2)
    221             cout<<"DRAW"<<endl;
    222         else
    223             cout<<"ALICE"<<endl;
    224     }
    225 }
    226 signed main()
    227 {
    228     fast;
    229     //freopen("input.txt", "rt", stdin);
    230     //freopen("output.txt", "wt", stdout);
    231     int t=1;
    232     cin>>t;
    233     int cas=1;
    234     while(cas<=t)
    235     {
    236     //cout<<"Case #"<<cas<<": ";
    237     shikhar7s(cas);
    238     cas++;
    239     }
    240     return 0;
    241 }
    242 ```
    243 
    244 [1527B2 - Palindrome Game (hard version)](/contest/1527/problem/B2 "Codeforces Round 721 (Div. 2)")
    245 
    246 Author: [DenOMINATOR](/profile/DenOMINATOR "Master DenOMINATOR")  
    247  Idea:[DenOMINATOR](/profile/DenOMINATOR "Master DenOMINATOR")
    248 
    249 **Editorial**
    250 
    251 Tutorial is loading...
    252 
    253 **Solution(Greedy) (DenOMINATOR)** 
    254 
    255 ```
    256 #include<bits/stdc++.h>
    257 using namespace std;
    258 
    259 void solve(){
    260 	int n;
    261 	cin >> n;
    262 	string s;
    263 	cin >> s;
    264 	bool is_palindrome=1;
    265 	int cnt_0 = 0, cnt_1 = 0;
    266 	for(int i=0;i<n;i++){
    267 		cnt_0 += s[i]=='0';
    268 	}
    269 	for(int i=0;i<n/2;i++){
    270 		if(s[i]!=s[n-1-i]) is_palindrome = 0;
    271 		if( (s[i]=='1' || s[n-1-i]=='1') && s[i]!=s[n-1-i]){
    272 			cnt_1++;
    273 		}
    274 	}
    275 	if(is_palindrome){
    276 		if(cnt_0 == 1){
    277 			cout << "BOB\n";
    278 			return;
    279 		}
    280 		if(cnt_0%2){
    281 			cout << "ALICE\n";
    282 			return;
    283 		}
    284 		cout << "BOB\n";
    285 		return;
    286 	}
    287 	if(cnt_0==2 && cnt_1==1){
    288 		cout << "DRAW\n";
    289 		return;
    290 	}
    291 	cout << "ALICE\n";
    292 	return;
    293 }
    294 
    295 signed main()
    296 {
    297 	int t;
    298 	cin >> t;
    299 	while(t--){
    300 		solve();
    301 	}
    302     return 0;
    303 }
    304 ```
    305 
    306 **Solution(DP) (DenOMINATOR)** 
    307 
    308 ```
    309 #include <bits/stdc++.h>
    310 using namespace std;
    311 
    312 typedef long long ll;
    313 double pi = acos(-1);
    314 #define _time_      1.0 * clock() / CLOCKS_PER_SEC
    315 #define fi          first
    316 #define se          second
    317 #define mp          make_pair
    318 #define pb          push_back
    319 #define all(a)      a.begin(),a.end()
    320 mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
    321 
    322 int dp[505][505][2][2];
    323 
    324 void precompute(){
    325     for(int i=0;i<=500;i++){
    326         for(int j=0;j<=500;j++){
    327             for(int k=0;k<2;k++){
    328                 for(int l=1;l>=0;l--){
    329                     dp[i][j][k][l] = 1e9;
    330                 }
    331             }
    332         }
    333     }
    334     dp[0][0][0][0]=0;
    335     dp[0][0][0][1]=0;
    336     for(int i=0;i<=500;i++){
    337         for(int j=0;j<=500;j++){
    338             for(int k=0;k<2;k++){
    339                 for(int l=1;l>=0;l--){
    340                     if(l==0 && j>0) dp[i][j][k][l] = min(dp[i][j][k][l],-dp[i][j][k][1]);
    341                     if(i>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i-1][j+1][k][0]);
    342                     if(j>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j-1][k][0]);
    343                     if(k==1) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j][0][0]);
    344                 }
    345             }
    346         }
    347     }
    348 }
    349 
    350 void solve(){
    351     int n;
    352     cin >> n;
    353     string s;
    354     cin >> s;
    355     int cnt00=0,cnt01=0,mid=0;
    356     for(int i=0;i<n/2;i++){
    357         if(s[i]=='0' && s[i]==s[n-i-1]) cnt00++;
    358         if(s[i]!=s[n-i-1]) cnt01++;
    359     }
    360     if(n%2 && s[n/2]=='0') mid=1;
    361     if(dp[cnt00][cnt01][mid][0]<0){
    362         cout << "ALICE";
    363     }else if(dp[cnt00][cnt01][mid][0]>0){
    364         cout << "BOB";
    365     }else{
    366         cout << "DRAW";
    367     }
    368 }
    369 
    370 int main(){
    371     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    372     //freopen("input.txt", "r", stdin);
    373     //freopen("output.txt", "w", stdout);
    374     #ifdef SIEVE
    375         sieve();
    376     #endif
    377     #ifdef NCR
    378         init();
    379     #endif
    380     precompute();
    381     int t;
    382     cin >> t;
    383     while(t--){
    384         solve();
    385         cout << "\n";
    386     }
    387     return 0;
    388 }
    389 ```
    390 
    391 [1527C - Sequence Pair Weight](/contest/1527/problem/C "Codeforces Round 721 (Div. 2)")
    392 
    393 Author: [sharabhagrawal25](/profile/sharabhagrawal25 "Master sharabhagrawal25")  
    394  Idea: [rivalq](/profile/rivalq "Master rivalq")
    395 
    396 **Editorial**
    397 
    398 Tutorial is loading...
    399 
    400 **Solution (sharabhagrawal25)** 
    401 
    402 ```
    403 #include <bits/stdc++.h>
    404 using namespace std;
    405 
    406 int main(){
    407         int t;
    408         cin >> t;
    409         while(t--){
    410             int n;
    411             cin >> n;
    412             
    413             int a[n];
    414             for (int i = 0 ; i < n; i++){
    415                 cin >> a[i];
    416             }
    417 
    418             vector <long long> dp(n, 0);
    419     
    420             map  <long long,long long> value;
    421     
    422             long long final_ans = 0;
    423     
    424             for (long long i = 0 ; i < n ; i++){
    425                 if (i > 0) dp[i] = dp[i - 1];
    426     
    427                 if (value.count(a[i])){
    428                     dp[i] += value[a[i]];
    429                 }
    430     
    431                 value[a[i]] += (i + 1);
    432                 final_ans += dp[i];
    433             } 
    434     
    435             cout << final_ans << endl;
    436         }
    437 }
    438 ```
    439 
    440 **Solution (mallick630)** 
    441 
    442 ```
    443 t = int(input())
    444 for j in range(t):
    445     n = int(input())
    446     a = list(map(int,input().split()))
    447     
    448     value = {}
    449     fa, ca = 0, 0
    450     
    451     for i in range(n):
    452       if a[i] in value:
    453         ca += value[a[i]]
    454       else:
    455         value[a[i]]=0
    456       value[a[i]] += i+1
    457       fa += ca
    458     
    459     print(fa)
    460 ```
    461 
    462 [1527D - MEX Tree](/contest/1527/problem/D "Codeforces Round 721 (Div. 2)")
    463 
    464 Author: [mallick630](/profile/mallick630 "Candidate Master mallick630")  
    465  Idea: [CoderAnshu](/profile/CoderAnshu "International Master CoderAnshu")
    466 
    467 **Editorial**
    468 
    469 Tutorial is loading...
    470 
    471 **Solution (shikhar7s)** 
    472 
    473 ```
    474 #include<bits/stdc++.h>
    475 using namespace std;
    476 #define int long long int
    477 #define mp(a,b) make_pair(a,b)
    478 #define vi vector<int>
    479 #define mii map<int,int>
    480 #define mpi map<pair<int,int>,int>
    481 #define vp vector<pair<int,int> >
    482 #define pb(a) push_back(a)
    483 #define fr(i,n) for(i=0;i<n;i++)
    484 #define rep(i,a,n) for(i=a;i<n;i++)
    485 #define F first
    486 #define S second
    487 #define endl "\n"
    488 #define Endl "\n"
    489 #define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    490 #define mod 1000000007
    491 #define dom 998244353
    492 #define sl(a) (int)a.length()
    493 #define sz(a) (int)a.size()
    494 #define all(a) a.begin(),a.end()
    495 #define pii pair<int,int> 
    496 #define mini 2000000000000000000
    497 #define time_taken 1.0 * clock() / CLOCKS_PER_SEC
    498 //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    499 //const long double pi = acos(-1);
    500 //mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    501 //primes for hashing 937, 1013
    502 template<typename T, typename U> static inline void amin(T &x, U y) 
    503 { 
    504     if (y < x) 
    505         x = y; 
    506 }
    507 template<typename T, typename U> static inline void amax(T &x, U y) 
    508 { 
    509     if (x < y) 
    510         x = y; 
    511 }
    512 vector<int> adj[200005];
    513 int vis[200005],c[200005],t;
    514 pii p[200005];
    515 void dfs(int x)
    516 {
    517     vis[x]=1;
    518     c[x]=1;
    519     int i;
    520     p[x]=mp(t,t);
    521     t++;
    522     fr(i,sz(adj[x]))
    523     {
    524         if(!vis[adj[x][i]])
    525         {
    526             dfs(adj[x][i]);
    527             c[x]+=c[adj[x][i]];
    528             p[x].S=p[adj[x][i]].S;
    529         }
    530     }
    531 }
    532 void shikhar7s(int cas)
    533 {
    534     int n,i;
    535     cin>>n;
    536     t=0;
    537     fr(i,n)
    538     {
    539         vis[i]=0;
    540         adj[i].clear();
    541     }   
    542     int x,y;
    543     fr(i,n-1)
    544     {
    545         cin>>x>>y;
    546         adj[x].pb(y);
    547         adj[y].pb(x);
    548     }
    549     dfs(0);
    550     int ans=0;
    551     fr(i,sz(adj[0]))
    552     {
    553         int x=c[adj[0][i]];
    554         x=(x*(x-1))/2;
    555         ans+=x;
    556     }
    557     cout<<ans<<" ";
    558     int s=0,ss=0,got=1;
    559     y=-1;
    560     fr(i,sz(adj[0]))
    561     {
    562         int x=c[adj[0][i]];
    563         if(p[adj[0][i]].F<=p[1].F&&p[adj[0][i]].S>=p[1].S)
    564         {
    565             y=adj[0][i];
    566             x-=c[1];
    567         }
    568         if(adj[0][i]!=y)
    569             got+=x;
    570         s+=x;
    571         x*=x;
    572         ss+=x;
    573     }
    574     ans=(s*s-ss)/2;
    575     ans+=s;
    576     cout<<ans<<" ";
    577     i=2;
    578     int l=0,r=1,j,b=0;
    579     while(i<n)
    580     {
    581         if((p[i].F<=p[l].F&&p[i].S>=p[l].S)||(p[i].F<=p[r].F&&p[i].S>=p[r].S))
    582         {
    583             cout<<0<<" ";
    584             i++;
    585             continue;
    586         }
    587         if(!l)
    588         {
    589             int f=2;
    590             ss=c[r];
    591             if(p[r].F<=p[i].F&&p[r].S>=p[i].S)
    592             {
    593                 f=1;
    594                 ss-=c[i];
    595             }
    596             if(!(p[y].F<=p[i].F&&p[y].S>=p[i].S))
    597             {
    598                 ans=1;
    599                 fr(j,sz(adj[0]))
    600                 {
    601                     int x=adj[0][j];
    602                     if(x==y)
    603                         continue;
    604                     int su=c[x];
    605                     if(p[x].F<=p[i].F&&p[x].S>=p[i].S)
    606                     {
    607                         f=0;
    608                         su-=c[i];
    609                     }
    610                     ans+=su;
    611                 }
    612             }
    613             else
    614                 ans=got;
    615             ans*=ss;
    616             cout<<ans<<" ";
    617             if(!f)
    618                 l=i;
    619             else if(f==1)
    620                 r=i;
    621             else
    622             {
    623                 i++;
    624                 b=1;
    625                 break;
    626             }
    627         }
    628         else
    629         {
    630             int f=2;
    631             s=c[l];
    632             ss=c[r];
    633             if(p[l].F<=p[i].F&&p[l].S>=p[i].S)
    634             {
    635                 f=0;
    636                 s-=c[i];
    637             }
    638             if(p[r].F<=p[i].F&&p[r].S>=p[i].S)
    639             {
    640                 f=1;
    641                 ss-=c[i];
    642             }
    643             ans=s*ss;
    644             cout<<ans<<" ";
    645             if(!f)
    646                 l=i;
    647             else if(f==1)
    648                 r=i;
    649             else
    650             {
    651                 i++;
    652                 b=1;
    653                 break;
    654             }
    655         }
    656         i++;
    657     }
    658     if(!b)
    659         cout<<1<<" ";
    660     else
    661     {
    662         while(i<=n)
    663         {
    664             cout<<0<<" ";
    665             i++;
    666         }
    667     }
    668     cout<<endl;
    669 }
    670 signed main()
    671 {
    672     fast;
    673     //freopen("output.txt", "rt", stdin);
    674     //freopen("output.txt", "wt", stdout);
    675     int t=1;
    676     cin>>t;
    677     int cas=1;
    678     while(cas<=t)
    679     {
    680     //cout<<"Case #"<<cas<<": ";
    681     shikhar7s(cas);
    682     cas++;
    683     }
    684     return 0;
    685 }
    686 ```
    687 
    688 **Solution (the_nightmare)** 
    689 
    690 ```
    691 #include<bits/stdc++.h>
    692 #include <ext/pb_ds/assoc_container.hpp>
    693 #include <ext/pb_ds/tree_policy.hpp>
    694 #define ll          long long
    695 #define pb          push_back
    696 #define ppb         pop_back
    697 #define endl        '\n'
    698 #define mii         map<ll,ll>
    699 #define msi         map<string,ll>
    700 #define mis         map<ll, string>
    701 #define rep(i,a,b)    for(ll i=a;i<b;i++)
    702 #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
    703 #define trav(a, x)  for(auto& a : x)
    704 #define pii         pair<ll,ll>
    705 #define vi          vector<ll>
    706 #define vii         vector<pair<ll, ll>>
    707 #define vs          vector<string>
    708 #define all(a)      (a).begin(),(a).end()
    709 #define F           first
    710 #define S           second
    711 #define sz(x)       (ll)x.size()
    712 #define hell        1000000007
    713 #define lbnd        lower_bound
    714 #define ubnd        upper_bound
    715 #define DEBUG       cerr<<"/n>>>I'm Here<<</n"<<endl;
    716 #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
    717 #define what_is(x)  cerr << #x << " is " << x << endl;
    718 #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
    719 #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    720 using namespace __gnu_pbds;
    721 using namespace std;
    722 #define PI 3.141592653589793
    723 #define N  200005
    724 ll add(ll x,ll y){return (x+y)%hell;}
    725 ll mul(ll x,ll y){return (x*y)%hell;}
    726 vector <ll> adj[N];
    727 ll subtree[N];
    728 ll min1[N];
    729 ll ans[N];
    730 ll vis[N];
    731 ll le;
    732 int v;int u;
    733 ll n;
    734 int prevv;int prevu;
    735 void init(){
    736     rep(i,0,n){
    737         adj[i].clear();
    738         subtree[i]=0;
    739         min1[i]=n;
    740         ans[i]=0;
    741         vis[i]=0;
    742     }
    743     le=n*(n-1)/2;
    744     v=0;u=0;
    745     prevv=-1;
    746     prevu=-1;
    747 }
    748 void dfs(int v,int prev=-1){
    749     subtree[v]=1;
    750     min1[v]=v;
    751     for (auto it: adj[v]){
    752         if (it==prev) continue;
    753         dfs(it,v);
    754         subtree[v]+=subtree[it];
    755         min1[v]=min(min1[v],min1[it]);
    756     }
    757 }
    758 void find(int val){
    759     //cout << v << " " << u << " " << prevv << " " << prevu << " " << val << endl;
    760     if (v==val or u==val){
    761         ll a,b;
    762         if (subtree[prevv]>subtree[v] or prevv==-1) a=subtree[v];
    763         else a=n-subtree[prevv];
    764         if (subtree[prevu]>subtree[u] or prevu==-1) b=subtree[u];
    765         else b=n-subtree[prevu];
    766         ans[val]=le-a*b;
    767         //cout << a << " " << b << endl;
    768         le=a*b;
    769         return;
    770     }
    771     for (auto it: adj[v]){
    772         if (it==prevv) continue;
    773         if (min1[it]==val){
    774             if (v==u) prevu=it;
    775             prevv=v;
    776             v=it;
    777             vis[it]=1;
    778             
    779             find(val);
    780             return;
    781         }  
    782     }
    783     for (auto it: adj[u]){
    784         if (it==prevu) continue;
    785         if (min1[it]==val){
    786             prevu=u;
    787             u=it;
    788             vis[it]=1;
    789             find(val);
    790             return;
    791         }  
    792     }
    793     ans[val]=le;
    794     le=0;
    795 }
    796 void solve()
    797 {
    798     cin >> n;
    799     init();
    800     rep(i,0,n-1){
    801         int x,y;
    802         cin >> x >> y;
    803         adj[x].pb(y);
    804         adj[y].pb(x);
    805     }
    806     dfs(0);
    807     //cout << le << endl;
    808     for (auto it: adj[0]) {ans[0]+=(subtree[it]*(subtree[it]-1))/2;}
    809     //cout << endl;
    810     //cout << ans[0] << endl;
    811     le-=ans[0];
    812     rep(i,1,n){
    813         if (vis[i]==1 or le==0) ans[i]=0;
    814         else find(i);
    815     }
    816     ans[n]=le;
    817     rep(i,0,n+1) cout << ans[i] << " ";
    818     cout << endl;
    819     return;
    820 }
    821 int main()
    822 {
    823     #ifndef ONLINE_JUDGE
    824     freopen ("input.txt","r",stdin);
    825     #endif
    826     ll int TEST=1;
    827     cin >> TEST;
    828     while(TEST--)
    829     {
    830         solve();
    831     }
    832 }
    833 ```
    834 
    835 [1527E - Partition Game](/contest/1527/problem/E "Codeforces Round 721 (Div. 2)")
    836 
    837 Author: [rivalq](/profile/rivalq "Master rivalq")  
    838  Idea: [rivalq](/profile/rivalq "Master rivalq")
    839 
    840 **Editorial**
    841 
    842 Tutorial is loading...
    843 
    844 **Solution (rivalq)** 
    845 
    846 ```
    847 #include<bits/stdc++.h>
    848 using namespace std;
    849 
    850 #define rep(i,a,n)     for(int i=a;i<n;i++)
    851 #define ll             long long
    852 //#define int            long long
    853 #define pb             push_back
    854 #define all(v)         v.begin(),v.end()
    855 #define endl           "\n"
    856 #define x              first
    857 #define y              second
    858 #define gcd(a,b)       __gcd(a,b)
    859 #define mem1(a)        memset(a,-1,sizeof(a))
    860 #define mem0(a)        memset(a,0,sizeof(a))
    861 #define sz(a)          (int)a.size()
    862 #define pii            pair<int,int>
    863 #define hell           1000000007
    864 #define elasped_time   1.0 * clock() / CLOCKS_PER_SEC
    865 
    866 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
    867 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
    868 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
    869 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
    870 
    871 const int N = 5e4+5;
    872 
    873 struct node{
    874     int a=0;
    875     node (int val=0){
    876         a=val;
    877     }
    878     void merge(node &n1,node &n2){
    879         this->a=min(n1.a,n2.a);
    880     }
    881 };
    882 struct update{
    883   int val=0;
    884   update(int t=0){
    885      val=t;
    886   }
    887   void combine(update &par,int tl,int tr){
    888       val+=par.val;
    889   }
    890   void apply(node &node){
    891       node.a+=val;
    892       val=0;
    893   }
    894 };
    895 template<typename node,typename update>
    896 struct segtree{
    897   node t[4*N];
    898   bool lazy[4*N];
    899   update zaker[4*N];
    900   int tl[4*N];
    901   int tr[4*N];
    902   node nul;
    903   inline void pushdown(int v){
    904      if(lazy[v]){    
    905        apply(zaker[v],v);
    906        lazy[v]=0;
    907        zaker[v].apply(t[v]);
    908      }
    909   }
    910   inline void apply(update &u,int v){
    911       if(tl[v]!=tr[v]){
    912           lazy[2*v]=lazy[2*v+1]=1;
    913           zaker[2*v].combine(u,tl[2*v],tr[2*v]);
    914           zaker[2*v+1].combine(u,tl[2*v+1],tr[2*v+1]);
    915       }
    916   }
    917   void build(int v,int start,int end,int arr[]){
    918       tl[v]=start;
    919       tr[v]=end;
    920       lazy[v]=0;
    921       zaker[v].val = 0;
    922       if(start==end){
    923           t[v].a=arr[start];
    924       }
    925       else{
    926           int m=(start+end)/2;
    927           build(2*v,start,m,arr);
    928           build(2*v+1,m+1,end,arr);
    929           t[v].merge(t[2*v],t[2*v+1]);
    930      }
    931   }
    932   void zeno(int v,int l,int r,update val){
    933       pushdown(v);
    934       if(tr[v]<l || tl[v]>r)return;
    935       if(l<=tl[v] && tr[v]<=r){
    936             t[v].a+=val.val;
    937             apply(val,v); 
    938             return;
    939       }
    940       zeno(2*v,l,r,val);
    941       zeno(2*v+1,l,r,val);
    942       t[v].merge(t[2*v],t[2*v+1]);
    943   }
    944   node query(int v,int l,int r){
    945       if(tr[v]<l || tl[v]>r)return node(hell);
    946       pushdown(v);
    947       if(l<=tl[v] && tr[v]<=r){
    948          return t[v];
    949       }
    950       node a=query(2*v,l,r);
    951       node b=query(2*v+1,l,r);
    952       node ans;
    953       ans.merge(a,b);
    954       return ans;
    955   }
    956 public:
    957   node query(int l,int r){
    958       return query(1,l,r);
    959   }
    960   void upd(int l,int r,update val){
    961       return zeno(1,l,r,val);
    962   }   
    963 };
    964 
    965 segtree<node,update>seg;
    966 
    967 int dp[101][N];
    968 
    969 int solve(){
    970  	      int n,k; cin >> n >> k;
    971               vector<int>a(n+1);
    972               rep(i,1,n+1){
    973                         cin >> a[i];
    974               }
    975               for(int i = 0; i <= n; i++){
    976                         for(int j = 0; j <= k; j++){
    977                                 dp[j][i] = hell;
    978                         }
    979               }
    980               dp[0][0] = 0;
    981               seg.build(1,0,n,dp[0]);
    982 
    983               for(int j = 1; j <= k; j++){
    984                                 vector<int>last(n+1);
    985                                 dp[j][0] = 0;
    986                                 for(int i = 1; i <= n; i++){
    987                                         if(last[a[i]] == 0){
    988                                                 last[a[i]] = i;
    989                                         }
    990                                         else{
    991                                                 seg.upd(0,last[a[i]]-1,i-last[a[i]]);
    992                                                 last[a[i]] = i;
    993                                         }
    994                                         dp[j][i] = seg.query(0,i-1).a;
    995 
    996                                 }
    997                                 seg.build(1,0,n,dp[j]);
    998                                 
    999               }
   1000               cout << dp[k][n] << endl;
   1001               //cout << elasped_time << endl;
   1002               return 0;
   1003 }
   1004 signed main(){
   1005     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   1006     //freopen("test.txt", "r", stdin);
   1007     //freopen("output.txt", "w", stdout);
   1008     #ifdef SIEVE
   1009     sieve();
   1010     #endif
   1011     #ifdef NCR
   1012     init();
   1013     #endif
   1014     int t=1;//cin>>t;
   1015     while(t--){
   1016         solve();
   1017     }
   1018     return 0;
   1019 }
   1020 ```
   1021 
   1022 **Solution (the_nightmare)** 
   1023 
   1024 ```
   1025 #include<bits/stdc++.h>
   1026 #include <ext/pb_ds/assoc_container.hpp>
   1027 #include <ext/pb_ds/tree_policy.hpp>
   1028 #define ll          long long
   1029 #define pb          push_back
   1030 #define ppb         pop_back
   1031 #define endl        '\n'
   1032 #define mii         map<ll,ll>
   1033 #define msi         map<string,ll>
   1034 #define mis         map<ll, string>
   1035 #define rep(i,a,b)    for(ll i=a;i<b;i++)
   1036 #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
   1037 #define trav(a, x)  for(auto& a : x)
   1038 #define pii         pair<ll,ll>
   1039 #define vi          vector<ll>
   1040 #define vii         vector<pair<ll, ll>>
   1041 #define vs          vector<string>
   1042 #define all(a)      (a).begin(),(a).end()
   1043 #define F           first
   1044 #define S           second
   1045 #define sz(x)       (ll)x.size()
   1046 #define hell        1000000007
   1047 #define lbnd        lower_bound
   1048 #define ubnd        upper_bound
   1049 #define DEBUG       cerr<<"/n>>>I'm Here<<</n"<<endl;
   1050 #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
   1051 #define what_is(x)  cerr << #x << " is " << x << endl;
   1052 #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
   1053 #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   1054 using namespace __gnu_pbds;
   1055 using namespace std;
   1056 #define PI 3.141592653589793
   1057 #define MAXN  35005
   1058 int tree1[4*MAXN];
   1059 int lazy[4*MAXN];
   1060 int s[MAXN];
   1061 void build(int node, int start, int end)
   1062 {
   1063     lazy[node]=0;
   1064     if(start == end)
   1065     {
   1066         // Leaf node will have a single element
   1067         tree1[node] = s[start];
   1068         //cout << tree1[node] << " ";
   1069     }
   1070     else
   1071     {
   1072         int mid = (start + end) / 2;
   1073         // Recurse on the left child
   1074         build(2*node, start, mid);
   1075         // Recurse on the right child
   1076         build(2*node+1, mid+1, end);
   1077         // Internal node will have the sum of both of its children
   1078         tree1[node] = min(tree1[2*node],tree1[2*node+1]);
   1079     }
   1080 }
   1081 void updateRange(int node, int start, int end, int l, int r, int val)
   1082 {
   1083     if (l>r) return;
   1084     if(lazy[node] != 0)
   1085     { 
   1086         // This node needs to be updated
   1087         tree1[node] = tree1[node]+lazy[node];    // Update it
   1088         if(start != end)
   1089         {
   1090             lazy[node*2] += lazy[node];                  // Mark child as lazy
   1091             lazy[node*2+1] += lazy[node];                // Mark child as lazy
   1092         }
   1093         lazy[node] = 0;                                  // Reset it
   1094     }
   1095     if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
   1096         return;
   1097     if(start >= l and end <= r)
   1098     {
   1099         // Segment is fully within range
   1100         tree1[node] = tree1[node]+val;
   1101         if(start != end)
   1102         {
   1103             // Not leaf node
   1104             lazy[node*2] += val;
   1105             lazy[node*2+1] += val;
   1106         }
   1107         return;
   1108     }
   1109     int mid = (start + end) / 2;
   1110     updateRange(node*2, start, mid, l, r, val);        // Updating left child
   1111     updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
   1112     tree1[node] = min(tree1[node*2],tree1[node*2+1]);        // Updating root with max value 
   1113 }
   1114 
   1115 ll queryRange(int node, int start, int end, int l, int r)
   1116 {
   1117     if(start > end or start > r or end < l)
   1118         return hell;         // Out of range
   1119     if(lazy[node] != 0)
   1120     {
   1121         // This node needs to be updated
   1122         tree1[node] = tree1[node]+lazy[node];            // Update it
   1123         if(start != end)
   1124         {
   1125             lazy[node*2] += lazy[node];         // Mark child as lazy
   1126             lazy[node*2+1] += lazy[node];    // Mark child as lazy
   1127         }
   1128         lazy[node] = 0;                 // Reset it
   1129     }
   1130     if(start >= l and end <= r)             // Current segment is totally within range [l, r]
   1131         return tree1[node];
   1132     int mid = (start + end) / 2;
   1133     ll p1 = queryRange(node*2, start, mid, l, r);         // Query left child
   1134     ll p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
   1135     return min(p1,p2);
   1136 }
   1137 void solve()
   1138 {
   1139     ll n,k;
   1140     cin >> n >> k;
   1141     int a[n];
   1142     rep(i,0,n) cin >> a[i];
   1143     int lastoc[n];
   1144     map <int,int> m1;
   1145     rep(i,0,n){
   1146         if (m1.find(a[i])==m1.end()) lastoc[i]=-1;
   1147         else lastoc[i]=m1[a[i]];
   1148         m1[a[i]]=i;
   1149     }
   1150     int dp[n][k+1];
   1151     dp[0][1]=0;
   1152     rep(i,1,n){
   1153         dp[i][1]=dp[i-1][1];
   1154         if (lastoc[i]!=-1) dp[i][1]+=i-lastoc[i];
   1155     }
   1156     rep(i,2,k+1){
   1157         rep(j,0,n) s[j]=dp[j][i-1];
   1158         build(1,0,n-1);
   1159         rep(j,0,i-1) dp[j][i]=hell;
   1160         dp[i-1][i]=0;
   1161         rep(j,i,n)
   1162         {
   1163             int lastj=lastoc[j];
   1164             if (lastj>0 and (i-2)<(lastj)) {
   1165                 updateRange(1,0,n-1,i-2,lastj-1,j-lastj);
   1166             } 
   1167             dp[j][i] = queryRange(1,0,n-1,i-2,j-1);
   1168         }
   1169     }
   1170     cout << dp[n-1][k] << endl;
   1171 }
   1172 int main()
   1173 {
   1174     #ifndef ONLINE_JUDGE
   1175     freopen ("input.txt","r",stdin);
   1176     #endif
   1177     ll int TEST=1;
   1178     //cin >> TEST;
   1179     //init();
   1180     while(TEST--)
   1181     {
   1182         solve();
   1183     }
   1184 }
   1185 
   1186 }
   1187 ```