Let $$$count$$$ be the number of $$$1's$$$ in the given binary string $$$S$$$.

Note that if we perform atleast one operation there will be atleast $$$k$$$ $$$0's$$$. So it is always optimal to get minimum $$$k$$$ $$$0's$$$ once we start doing operations.

Let $$$S$$$ = $$$s_1s_2s_3s_4s_5s_6s_7s_8s_9s_{10}$$$ and $$$k = 3$$$

we can do operations in the following way to get $$$k$$$ $$$0's$$$.

1. Choose $$$i=3$$$, $$$S$$$ = $$$111000s_7s_8s_9s_{10}$$$

2. Choose $$$i=6$$$, $$$S$$$ = $$$111111000s_{10}$$$

3. Choose $$$i=7$$$, $$$S$$$ = $$$1111111000$$$.

By this way we can always get minimum of $$$k$$$ $$$0's$$$ once we start doing operations.

Hence, the answer to the problem is maximum( $$$count$$$ , $$$n-k$$$ ).

Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int ans=count(s.begin(),s.end(),'1');
        ans=max(ans,n-k);
        cout<<ans<<"\n";
    }
}

From the above problem, we can know what are the maximum possible $$$1's$$$ in $$$S$$$ we can get for a given $$$k$$$. Now we have to think minimum operations required to get those maximum $$$1's$$$. For given $$$i$$$ let's call $$$S_{i},S_{i-1},S_{i-2},...,S_{i-k+2},S_{i-k+1}$$$ as Left part and $$$S_{i+1},S_{i+2},S_{i+3},...,S_{i+k-1},S_{i+k}$$$ as Right part. It is easy to see that If we wish to do operation then there will be atleast one $$$0$$$ in Left part makes the operation optimal(Because it will decrease the $$$0$$$ count and gradually increase the $$$1$$$ count). So we can come to conclusion that, whenever we have to do the operation, Left part have more number of $$$0's$$$ and $$$S_1 = S_2 = S_3 = ... = S_{i-k} = 1$$$.

Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s;
        cin>>s;
        ll ind1=-1,ind2=-1;
        for(ll i=0;i<n;i++){
            if(s[i]=='0') ind2=i;
        }
        for(ll i=n-1;i>=0;i--){
            if(s[i]=='0') ind1=i;
        }
        ll cnt=count(s.begin(),s.end(),'1');
        for(ll k=1;k<=(n/2);k++){
            if(cnt>=(n-k)) cout<<"0 ";
            else{
                ll l=ind1,r=ind2;
                r-=k;
                cout<<(r-l+k)/k<<" ";
            }
        }
        cout<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        for(ll i=0;i<n;i++) cout<<i+1<<" ";
        cout<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;
const ll N=3e5+11;
vector<ll> v;
 
int main(){
    fast;
    v.resize(N);
    v[1]=1;
    v[2]=2;
    ll val=3,diff=3;
    for(ll i=3;i<N;i+=2){
        v[i]=(v[i-1]*(val%mod))%mod;
        v[i+1]=(v[i]*2)%mod;
        val+=diff;
        diff++;
    }
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<v[n]<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll mod=1e9+7;
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll m,n;
        cin>>m>>n;
        string s;
        cin>>s;
        if(m>n) cout<<"0\n";
        else{
            vector<ll> dp(n+1);
            dp[0]=1;
            for(ll i=0;i<n;i++){
                vector<ll> ndp(n+1);
                for(ll j=0;j<=i;j++){
                    ndp[j+1]=(ndp[j+1]+dp[j])%mod;
                    if(j>0) ndp[j-1]=(ndp[j-1]+(26*dp[j])%mod)%mod;
                    else ndp[j]=(ndp[j]+dp[j])%mod;
                }
                dp=ndp;
            }
            cout<<dp[m]<<"\n";
        }
    }
}

It is easy to see that, for a given query we need the count of the lowerbound of given $$$x$$$ in $$$l$$$ to $$$r$$$ segment.

This can be done using various data structures, but in Merge sort tree the constant factor is high so it will give TLE if you didn't implement it properly.

The below solution is based on square-root decomposition.

Time Complexity : $$$O(n\sqrt{n})$$$

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
//#define int long long
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=1000000001;
const int B=3000;//100;
int T,n,q;
int a[N],bnum[N];

/*
struct cmp1 	//自定义升序
{
    bool operator()(pair<int,int> v1,pair<int,int> v2)
    {
        return v1.first < v2.first;
    }
};

struct cmp2 	//自定义降序
{
    bool operator()(pair<int,int> v1,pair<int,int> v2)
    {
        return v1.first > v2.first;
    }
};
*/

struct block
{
    set<pair<int,int> >    S;
    unordered_map<int,int> cnt;
}blk[N];

void init()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n+4;i++)
    {
        blk[i].S.clear();
        blk[i].cnt.clear();
    }
    for(int i=1;i<=n;i++)
    {
        bnum[i]=i/B+1;
        blk[bnum[i]].S.insert(make_pair(a[i],i));
        blk[bnum[i]].cnt[a[i]]++;
    }
}

void solve()
{
    for(int i=1;i<=q;i++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int l,r,x,mxl=-INF,cl=0,mnr=INF,cr=0; //l:<x,r:>=x
            cin>>l>>r>>x;
            if(bnum[l]==bnum[r])
            {
                for(int i=l;i<=r;i++)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
            }
            else
            {
                for(int i=l;bnum[i]==bnum[l];i++)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
                for(int i=r;bnum[i]==bnum[r];i--)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
                for(int i=bnum[l]+1;i<=bnum[r]-1;i++)
                {
                    set<pair<int,int> >::iterator it=blk[i].S.lower_bound(make_pair(x,0));
                    if(it!=blk[i].S.end())
                    {
                        if(it->first<mnr) mnr=it->first,cr=blk[i].cnt[it->first];
                        else if(it->first==mnr) cr+=blk[i].cnt[it->first];
                    }
                    if(it==blk[i].S.begin()) continue;
                    it--;
                    if(it->first>mxl) mxl=it->first,cl=blk[i].cnt[it->first];
                    else if(it->first==mxl) cl+=blk[i].cnt[it->first];
                }
            }
            //
            //cout<<"mxl="<<mxl<<" mnr="<<mnr<<'\n';
            //
            if(mxl==-INF) cout<<cr<<'\n';
            else if(mnr==INF) cout<<cl<<'\n';
            else if(x-mxl==mnr-x) cout<<cl+cr<<'\n';
            else if(x-mxl<mnr-x) cout<<cl<<'\n';
            else cout<<cr<<'\n';
        }
        else
        {
            int p,v;
            cin>>p>>v;
            blk[bnum[p]].S.erase(make_pair(a[p],p));
            blk[bnum[p]].cnt[a[p]]--;
            a[p]=v;
            blk[bnum[p]].S.insert(make_pair(a[p],p));
            blk[bnum[p]].cnt[a[p]]++;
        }
    }
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

signed main()
{
    fastio;

	cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

Lets root the tree at any node, let $$$r$$$ be the root of the tree.

We can solve the problem using $$$DP$$$ in the following way:

$$$dp1[i][j]$$$ = The minimum beauty of the component that contains node $$$i$$$, when the subtree rooted at node $$$i$$$ is divided into exactly $$$j$$$ components, such that the colour of all nodes containing in the component where node $$$i$$$ is included is red.

$$$dp2[i][j]$$$ =The minimum beauty of the component that contains node $$$i$$$, when the subtree rooted at node $$$i$$$ is divided into exactly $$$j$$$ components, where all components except the one containing node $$$i$$$ doesn't satisfy the condition of "Perfect Tree"(i.e., all other components are non-perfect trees).

If there is no value for particular $$$DP$$$ state, then set it into $$$♾️$$$.

The answer to problem is $$$j-1$$$ where $$$dp1[r][j]<♾️$$$ or $$$dp2[r][j] < 0$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll n;
vector<ll> a;
vector<vector<ll>> adj;

vector<pair<ll,ll>> dfs(ll x, ll p){
    vector<pair<ll,ll>> dp;
    dp.push_back({0,1e18});
    for(auto i:adj[x]){
        if(i!=p){
            vector<pair<ll,ll>> dp1=dfs(i,x);
            ll n1=(ll)dp1.size();
            dp1.push_back({1e18,1e18});
            for(ll j=n1-1;j>=0;j--){
                if(dp1[j].first<1e18 || dp1[j].second<0){
                    dp1[j+1].first=min((ll)0,dp1[j+1].first);
                }
            }
            ll n2=(ll)dp.size()-1;
            vector<pair<ll,ll>> dp2(n1+n2+1,{1e18,1e18});
            for(ll j=0;j<=n2;j++){
                for(ll k=0;k<=n1;k++){
                    dp2[j+k].first=min(dp2[j+k].first,dp[j].first+dp1[k].first);
                    dp2[j+k].second=min(dp2[j+k].second,dp[j].first+dp1[k].second);
                    dp2[j+k].second=min(dp2[j+k].second,dp[j].second+dp1[k].first);
                    dp2[j+k].second=min(dp2[j+k].second,dp[j].second+dp1[k].second);
                }
            }
            dp=dp2;
        }
    }
    ll n2=(ll)dp.size()-1;
    vector<pair<ll,ll>> dp2(n2+1);
    for(ll i=0;i<=n2;i++){
        if(a[x]>0){
            dp2[i].first=dp[i].first+a[x];
            dp2[i].second=dp[i].second+a[x];
        }
        else{
            dp2[i].first=1e18;
            dp2[i].second=min(dp[i].first,dp[i].second)+a[x];
        }
    }
    return dp2;
}
 
int main(){
    fast;
    ll t;
    t=1;
    while(t--){
        cin>>n;
        a.clear();
        a.resize(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        string s;
        cin>>s;
        for(ll i=0;i<n;i++){
            if(s[i]=='1') a[i]=-a[i];
        }
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<pair<ll,ll>> dp=dfs(0,-1);
        for(ll i=0;i<n;i++){
            if(dp[i].first<1e18 || dp[i].second<0){
                cout<<i;
                break;
            }
        }
    }
}