$$$\mathcal Brief\;\mathcal Solution :$$$

A $$$n$$$-regular convex polygon is beautiful if and only if $$$n \% 4 = 0$$$. ($$$\%$$$ is the modular arithmetic symbol)

t = int(input())
for testcase in range(t):
    n = int(input())
    if(n%4 == 0) :
        print("Yes")
    else :
        print("No")

#include <iostream>
 
using namespace std;
 
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        if(n % 4 == 0){
            cout << "YES\n";
        }
        else cout << "NO\n";
    }
}

$$$\mathcal Brief\;\mathcal Solution :$$$

If the string $$$s$$$ is non-decreasing, then the answer is $$$s$$$ itself, otherwise the answer is $$$x+1$$$ zeroes and $$$y$$$ ones, where $$$x$$$ is the number of leading zeroes of the string $$$s$$$, and $$$y$$$ is the number of trailing ones of the string $$$s$$$.

t = int(input())
for testcase in range(t):
    n = int(input())
    s = input()
    lef, rig, sw = 1, 1, 0
    for i in range(n-1):
        if(s[i] > s[i+1]):
            sw = 1
            break
    if(sw == 0):
        print(s)
        continue
    for i in range(n):
        if (s[i] == '1'):
            lef = i
            break
    for i in range(n-1, 0, -1):
        if (s[i] == '0'):
            rig = i
            break
    st = s[:lef] + '0' + s[rig+1:]
    print(st)

#include <iostream>
#include <string>
 
using namespace std;
 
int main(){
    
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int sw = 1;
        for(int i = 1; i < s.size(); i++){
            if(s[i] < s[i-1])sw = 0;
        }
        if(sw){
            cout << s << '\n';
            continue;
        }
        string ans;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '1')break;
            ans.push_back('0');
        }
        ans.push_back('0');
        for(int i = s.size()-1; i >= 0; i--){
            if(s[i] == '0')break;
            ans.push_back('1');
        }
        cout << ans << '\n';
    }
}

$$$\mathcal Brief\; \mathcal Solution$$$ :

Give greatest elements to friends with $$$w_i = 1$$$. For the rest sort the elements in non-descending order of $$$a_i$$$ and sort the friends in non-ascending order of $$$w_i$$$ then give first $$$w_1-1$$$ elements to friend $$$1$$$, next $$$w_2-1$$$ elements to friend $$$2$$$ and so on, also give $$$k-i+1$$$-th greatest element to friend $$$i$$$ $$$(1 \le i \le k)$$$.

t = int(input())
for tc in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    w = list(map(int, input().split()))
    a.sort(reverse = True)
    w.sort()
    ii, l, r = k, 0, n-1
    ans = 0
    for i in range(k):
        if(w[i] > 1):
            ii = i
            break
        ans = ans+a[l]*2
        l = l+1
    for u in range(k-1, ii-1, -1):
        i = w[u]
        ans = ans + a[l] + a[r]
        r = r-i+1
        l = l+1
    print(ans)

#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define int ll

using namespace std;
const int MN = 2e5+7;

vector<int> v[MN];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        for(int i = 0; i <= n; i++)v[i].clear();
        ll a[n], w[k];
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        for(int i = 0; i < k; i++){
            cin >> w[i];
        }
        sort(w, w+k);
        sort(a, a+n);
        for(int i = 0; i < k/2; i++)swap(w[i], w[k-i-1]);
        int po = 0;
        for(int i = 0; i < n-k; i++){
            while(w[po] == v[po].size()+1)po++;
            v[po].push_back(a[i]);
        }
        ll ans = 0;
        int qf = 1;
        for(int i = 0; i < k; i++){
            ans += a[n-i-1];
            if(v[i].size())ans += v[i][0];
            else ans += a[n-qf], qf++;
        }
        
        cout << ans << '\n';
    }
}

$$$\mathcal Brief \mathcal Solution$$$ :

Realize that a RDB of level $$$i$$$ is consisted of a vertex (the root of the RDB of level $$$i$$$) connected to the roots of two RDBs of level $$$i-2$$$ and a RDB of level $$$i-1$$$.

Run a DP and calculate the answer for each level $$$i$$$ ($$$ 3 \le i \le 2 \cdot 10^6$$$), then $$$dp_i = 2 \cdot dp_{i-2} + dp_{i-1} + (i \% 3 == 0?4:0)$$$.

v = []
v.append(0)
v.append(0)
v.append(0)
v.append(4)
v.append(4)
mod = int(1e9+7)
for i in range (5, 2000010):
    v.append(max(((2*v[i-2])+v[i-1])%mod,((4*v[i-4])+4*v[i-3]+v[i-2]+4)%mod))
t = int(input())
for _ in range(t):
    print(v[int(input())])

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int mod = int(1e9+7);
const int MN = int(2e6+7);

int dp[MN];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    dp[0] = dp[1] = 0;
    dp[2] = 4;
    for(int i = 3; i < MN; i++){
        long long w = dp[i-1];
        w += 2*dp[i-2] + (i % 3 == 2)*4;
        w %= mod;
        dp[i] = w;
    }

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        n--;
        cout << dp[n]%mod << '\n';
    }
}

$$$\mathcal Hints$$$ :

1. Find some greedy approaches. Its guessable that the problem is greedy.

2. Define $$$s_i$$$ for food $$$i$$$ equal to the number of guys who likes food $$$i$$$. Then find some condition which is enough to be sure that no answer exist.

3. See the last friend in a suitable permutation. What food will he eat?

4. Its easy to see that if $$$\forall 1 \le i \le m \Rightarrow s_i > w_i$$$, then no answer exist.

5. If a food $$$i$$$ exist such that $$$s_i \le w_i$$$, then what will happen to the friends who like this food? They can always eat this food no matter what happens, so lets call them as late as possible(so its less likely for them to eat more than one plate). Now continue the process with rest of the friends and foods.

$$$\mathcal Brief\;\mathcal Solution$$$ :

Define $$$s_i$$$ equal to the number of friends who likes food $$$i$$$. If for some $$$i$$$, $$$s_i \le w_i$$$ then place all the friends who likes food $$$i$$$ in the end of the permutation and erase them and continue doing the same thing for the rest of the friends and foods

It's easy to see that if the set of friends became empty then the permutation we constructed is suitable(and no one would eat Lee), otherwise Lee has to buy more food!!

import sys
import heapq

inputarray = [int(x) for x in sys.stdin.read().split()]

n, m = inputarray[0], inputarray[1]

s, w = [], []
for i in range(2, n+2):
    w.append(inputarray[i])

g, eg, foodm, friendm, x, y = [], [], [], [], [], []

for i in range(n):
    s.append(0)
    foodm.append(0)
    g.append([])

for i in range(m):
    friendm.append(0)
    x.append(0)
    y.append(0)
    
inppo = n+2
for i in range(m):
    x[i], y[i] = inputarray[inppo], inputarray[inppo+1]
    inppo = inppo+2
    x[i] = x[i]-1
    y[i] = y[i]-1
    u = x[i]
    v = y[i]
    s[u] = s[u]+1
    s[v] = s[v]+1
    g[u].append(i)
    g[v].append(i)
    eg.append((v, u))

myq = []

ans = []

for i in range(n):
    heapq.heappush(myq, (-w[i]+s[i], i))

while len(myq): 
    u = myq[0]
    heapq.heappop(myq)
    if u[0] != -w[u[1]]+s[u[1]]:
        continue
    if(u[0] > 0):
        print("DEAD")
        sys.exit()
    foodm[u[1]] = 1
    sw = 1
    for i in g[u[1]]:
        if friendm[i] == 0:
            friendm[i] = 1
            if y[i] == u[1]:
                x[i], y[i] = y[i], x[i]
            s[x[i]] = s[x[i]]-1
            s[y[i]] = s[y[i]]-1
            heapq.heappush(myq, (-w[y[i]]+s[y[i]], y[i]))
            ans.append(i)
            if(len(ans) == m):
                sw = 0
                break;
    if(sw == 0):
        break
print("ALIVE")
for i in ans[::-1]:
    print(i+1, end=" ")

#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;
const int MN = 2e5+7;

int x[MN], y[MN], s[MN], w[MN], mark[MN], colmark[MN];

vector<int> v[MN], a;
vector<pii> f;

priority_queue<pii, vector<pii>, greater<pii>> pq;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)cin >> w[i];
    for(int i = 0; i < m; i++){
        cin >> x[i] >> y[i];
        s[x[i]]++;
        s[y[i]]++;
        v[x[i]].push_back(i);
        v[y[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        if(s[i])pq.push({max(0, s[i]-w[i]), i});
        else colmark[i] = 1;
    }

    while(pq.size()){
        auto q = pq.top();
        pq.pop();
        if(q.fr != max(0, s[q.sc]-w[q.sc]))continue;
        if(q.fr > 0){
            cout << "DEAD\n";
            exit(0);
        }
        int id = q.sc;
        vector<int> wt;
        for(auto u : v[id]){
            if(mark[u])continue;
            a.push_back(u);
            if(x[u] == id)
                swap(x[u], y[u]);
            if(!colmark[x[u]])wt.push_back(x[u]);
            mark[u] = 1;
        }
        sort(all(wt));
        for(int i = 0; i < wt.size(); i++){
            s[wt[i]]--;
            if(i == wt.size()-1 || wt[i+1] != wt[i]){
                if(s[wt[i]]){
                    if(max(0, s[wt[i]]-w[wt[i]]) == 0)colmark[wt[i]] = 1;
                    pq.push({max(0, s[wt[i]]-w[wt[i]]), wt[i]});
                }
            }
        }
    }
    cout << "ALIVE\n";
    for(int i = 0; i < a.size()/2; i++)swap(a[i], a[a.size()-i-1]);
    for(auto u : a){
        cout << u+1 << ' ';
    }
    cout << '\n';
}

$$$\mathcal Brief\; \mathcal Solution$$$ :

Define $$$win_{s,\,e}$$$ ($$$s \le e$$$) equal to $$$1$$$ if Lee can win the game when $$$s$$$ is written on the board, and equal to $$$0$$$ otherwise, also define $$$lose_{s,\,e}$$$ the same way.

Win :

If $$$e$$$ is odd then if $$$s$$$ is odd Lee loses otherwise Lee wins. So if $$$e$$$ is even then :

• if $$$\frac e 2 < s \le e$$$ then if $$$s$$$ is odd then Lee wins, otherwise Lee loses;
• if $$$\frac e 4 < s \le \frac e 2$$$ then Lee wins;
• if $$$s \le \frac e 4$$$ then the answer is equal to $$$win_{s,\, \lfloor \frac e 4 \rfloor}$$$.

Lose :

If $$$e < 2 \cdot s$$$, then Lee can immediately lose, otherwise the answer is equal to $$$\displaystyle win_{s,\, \lfloor \frac e 2 \rfloor}$$$.

import sys

inpy = [int(x) for x in sys.stdin.read().split()]

def win(s, e) :
    if e == s :
        return False
    if e == s+1 :
        return True
    if e % 2 == 1 :
        if s % 2 == 1 :
            return False
        return True
    q = e//4
    
    if s <= q :
        return win(s, q)
    q = e//2
    if(s > q) :
        return (e-s) % 2 == 1
    return True

def lose(s, e) :
    q = e//2
    if(s > q) :
        return True
    else :
        return win(s, q)

t = inpy[0]
start = (True, False)
inpo = 1
v = (True, True)

for tc in range(t):
    if(inpo+1 >= len(inpy)) :
        print('wtf')
    s, e = inpy[inpo], inpy[inpo+1]
    inpo = inpo+2
    v = ((win(s, e), lose(s, e)))
    if start[0] and start[1] :
        break
    if (not start[0]) and (not start[1]) :
        break
    if start[1] :
        v = (not v[0], not v[1])
    start = (v[1], v[0])

if((start[0] != True and start[0] != False) or (start[1] != True and start[1] != False)) :
    print('wtf')
sw = 2
if start[1] :
    sw = sw-1
    print(1, end = ' ')
else :
    sw = sw-1
    print(0, end = ' ')
if start[0] :
    print(1)
    sw = sw-1
else :
    print(0)
    sw = sw-1
if sw :
    print(wtf)

#include <iostream>
#include <vector>
#include <string>
#define fr first
#define sc second
#define ll long long
#define int ll

using namespace std;

const int MN = 1e5+7;

pair<int, int> c[MN];

int chk(ll s, ll e){
    if(e == s)return 0;
    if(e == s+1)return 1;
    if(e & 1){
        if(s & 1)return 0;
        return 1;
    }
    if(s <= e/4)
        return chk(s, e/4);
    if(s > (e/4)*2)return ((e-s)&1);
    else return 1;
}

int lck(ll s, ll e){
    if(s*2 > e)return 1;
    int w = e/2 + 3;
    while(w*2 > e)w--;
    return chk(s, w);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        ll x, y;
        cin >> x >> y;
        c[i] = {chk(x, y), lck(x, y)};
    }

    int f = 1;
    int s = 0;
    for(int i = 0; i < n; i++){
        if(f == 1 && s == 1)break;
        if(f == 0 && s == 0)break;
        if(s == 1) c[i].fr^=1, c[i].sc^=1;
        f = c[i].sc;
        s = c[i].fr;
    }
    cout << s << ' ' << f << '\n';
}

void dfs(int nw, int parent){
      int fixDPnow = dp[nw], fixDPv;
      for(v in children of nw){//skip v == parent
            fixDPv = dp[v];
            move(nw, v);//it will move the root from nw to v and updates dp
            dfs(v, nw);
            //following two lines will move the root to nw and update dp
            dp[v] = fixDPv;
            dp[nw] = fixDPnow;
      }
}

int main(){
      calculateDP(rat);//it will calculate the DP when the root is rat
      dfs(rat, rat);//this will move the root to all the vertices
}

void dfs(int nw, int parent){
      store dp[nw] as the answer to f(nw, nw);
      int fdpnw = dp[nw], fdpu;
      for(u in children of nw){//skip u == parent
            fdpu = dp[u];

            store dp[u] as the answer to f(nw, u);
            moveto(nw, u);//moving root to u

            store dp[nw] as the answer to f(u, nw);
            dfs(u, nw);//calculate the data for all vertices in the subtree of u

            dp[nw] = fdpnw; dp[u] = fdpu;//moving root to nw
      }
}

int main(){
      calculateDP(1);//calculates dp when root is 1
      dfs(1, 1);//it will move the root to all the vertices and calculates the data needed.
      int q;
      cin >> q;
      while(q--){
            int r, u;
            cin >> r >> u;
            if(r == u){
                  cout << f(r, u) << '\n'; //using the calculated data
                  continue;
            }
            if(u is not an ancestor of r){
                  cout << f(par[u], u) << '\n'; //using the calculated data
            }
            else{
                 r = rise(r, u);//its O(log_2n)
                 cout << f(r, u) << '\n'; //again using the calculated data
            }
      }
}

#include <bits/stdc++.h>
#define fr first
#define sc second

using namespace std;
const int MN = 2e5+7;

int dp[MN], dep[MN], timer, l, n, ans[MN], tin[MN], tout[MN];
vector<int> g[MN];
map<pair<int, int>, int> data;
vector<vector<int>> up;

bool is_ancestor(int u, int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int rise(int u, int v){
    if(dep[u] == dep[v]+1)return u;
    int ln = dep[u] - dep[v] - 1;
    int c = 0;
    while(ln){
        if(ln & 1)u = up[u][c];
        ln >>= 1;
        c++;
    }
    return u;
}

void cal(int nw, int pr){
    dp[nw] = 1;
    for(auto u : g[nw]){
        if(u == pr)continue;
        cal(u, nw);
        dp[nw] += dp[u];
    }
}

void store(int r, int u, int vl){
    data[{r, u}] = vl;
}

void dfs(int nw, int pr){
    int v = nw;

    tin[v] = ++timer;
    up[v][0] = pr;
    for (int i = 1; (1 << i) <= dep[v]; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for(auto u : g[nw]){
        if(u == pr)continue;
        dep[u] = dep[nw]+1;
        int fdpnw = dp[nw], fdpu = dp[u];

        store(nw, u, dp[u]);

        dp[nw] -= dp[u];
        dp[u] += dp[nw];

        store(u, nw, dp[nw]);
        dfs(u, nw);

        dp[nw] = fdpnw;
        dp[u] = fdpu;
    }

    tout[nw] = ++timer;
}

void preprocess(int root) {
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int q;
    cin >> n >> q;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cal(0, 0);
    for(int i = 0; i < n; i++)ans[i] = dp[i];
    preprocess(0);

    while(q--){
        int u, r;
        cin >> r >> u;
        r--; u--;
        if(r == u){
            cout << n << '\n';
            continue;
        }
        if(is_ancestor(u, r)){
            r = rise(r, u);
            cout << data[{r, u}] << '\n';
        }
        else{
            cout << ans[u] << '\n';
        }
    }
}