• Excellent:
• Great:
• Good:
• Average:
• Bad:
• Trash:
• Worst:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

# author: khba
for _ in range(int(input())):
    a, b, c, d = map(int, input().split())
    print('YES' if a == b == c == d else 'NO')

// author: khba
#include <iostream>
using namespace std;

int cnt1[26], cnt2[26];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        for (int i = 0; i < 26; ++i) cnt1[i] = cnt2[i] = 0;
        int n;
        cin >> n;
        string s, t;
        cin >> s >> t;
        for (char &c : s) cnt1[c - 'a'] ++;
        for (char &c : t) cnt2[c - 'a'] ++;
        bool answer = true;
        for (int i = 0; i < 26; ++i)
            if (cnt1[i] != cnt2[i]) 
                answer = false;
        puts(answer ? "YES" : "NO");
    }
}

// author: khba
#include <iostream>
using namespace std;

int main()
{
    int t; 
    cin >> t;
    while (t--) {
        
        int n;
        cin >> n;
        bool odd = false, even = false;
        int a[n];
        for (int i = 0, x; i < n; ++i) {
            cin >> a[i];
            if (a[i] % 2 == 0) even = true;
            else odd = true;
        }
        if (odd and even) sort(a, a + n);
        for (int i = 0; i < n; ++i) cout << a[i] << " \n"[i == n - 1]; 
    }
}

Answer is always prime number, try to prove why.

Notice how equation works if $$$x$$$ does not satisfy property.

It means that for each $$$i$$$, $$$a_{i} \equiv 0 \ (mod \ x)$$$

// Author: BehruzbekX
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    using ll = long long;
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        for (auto &i: a) cin >> i;
        for (ll x : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}) {
            int ok = 0;
            for (ll i : a) {
                if (i % x) {
                    ok = 1;
                    break;
                }
            }
            if (ok) {
                cout << x << '\n';
                break;
            }
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k, x;
        cin >> n >> k >> x;
        vector<int> a(n);
        for (int &i : a) cin >> i;
        a.push_back(-1e9);
        a.push_back(1e9);
        n += 2;
        sort(a.begin(), a.end());
        int l = 0, r = x + 1;
        while (l + 1 < r) {
            int m = (l + r) >> 1, f = 0;
            a[0] = - m, a[n - 1] = x + m;
            for (int i = 1; i < n; ++i) f += max(0, (a[i] - m) - (a[i - 1] + m) + 1);
            if (f >= k) l = m;
            else r = m;
        }
        a[0] = - l, a[n - 1] = x + l;
        int j = 0;
        for (int i = 1; i < n; i++)
    		for (j = max(j, a[i - 1] + l); j <= min((a[i] - l), x) && k; j++)
    			cout << j << ' ', k--;
    	cout << '\n';
    }
    return 0;
}

We don't need to know lowest common ancestor (LCA) to solve this problem. Think of subtree sizes to replace LCA.

Let $$$sz_{i} = $$$ subtree size of $$$i$$$ when root is $$$r$$$. In order for $$$i$$$ to be able to be in the $$$S_{r}$$$: $$$sz_{i} \geq k$$$ must hold.

Notice how instead of calculating the answer for each root, we can calculate contribution of $$$i$$$ when root is $$$1 \ldots n$$$.

// Author: BehruzbekX
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    using ll = long long;
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<vector<int>> a(n);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v, --u, --v;
            a[u].emplace_back(v);
            a[v].emplace_back(u);
        }
        ll ans = 0; 
        vector<int> sz(n, 1); // initial subtree sizes
        auto dfs = [&] (auto &dfs, int v, int p) -> void{ // performing DFS in the tree
            for (int u : a[v]) {
                if (u != p) { // to avoid visiting parent again
                    dfs(dfs, u, v); // recursively visit subtree
                    sz[v] += sz[u]; // merge
                }
            }
        };
        /*
            |S_1| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is 1)
            |S_2| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is 2)
            |S_3| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is 3)
            ...                                                    (root is i)
            |S_n| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is n)
            We should add them for each node (calculating contribution):
        */
        dfs(dfs, 0, -1); // Arbitrary starting point
        for (int i = 0; i < n; i++) {
            if (n - sz[i] >= k) ans += sz[i]; 
            if (sz[i] >= k) ans += n - sz[i]; 
        }
        cout << ans + n << '\n';  
    }
}

Find the answer for each $$$i$$$ ($$$|S_{1}|, |S_{2}|, |S_{3}|, \ldots , |S_{n}|$$$).

Let us have the answer for $$$dp_{v} = $$$ answer when root is $$$v$$$, let $$$u$$$ be the directly connected node to $$$v$$$. How $$$dp_{v}$$$ changes when we make root $$$u$$$ ($$$dp_{u}$$$)?

First, we calculate the answer for each $$$i$$$ (the subtree of $$$i$$$) and subtree sizes, where the starting point is arbitrary.

Let's go back to our hint. Suppose we already have the answer for $$$dp_{v}$$$.
To get the answer for $$$dp_{u}$$$, we need to understand how the answer changes based on the subtree of $$$u$$$ and the part outside it.

This technique is known as Rerooting. When we transition from $$$v$$$ to $$$u$$$, we divide the total contribution into two parts:
1. inside the subtree of $$$u$$$, and
2. outside the subtree of $$$u$$$.

If $$$n - sz_{u} \lt k$$$, then we should subtract that contribution from $$$dp_{v}$$$ — this corresponds to the part outside the subtree of $$$u$$$, because when $$$u$$$ becomes root, $$$v$$$ have no longer subtree of $$$u$$$ as a subtree, which implies that we need to remove contribution of it. As for the subtree of $$$u$$$: if $$$sz_{u} \lt k$$$, then the answer increases by one because $$$n \ge k$$$.

Finally, the transition becomes:

// Author: BehruzbekX
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    using ll = long long;
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<vector<int>> a(n);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v, --u, --v;
            a[u].emplace_back(v);
            a[v].emplace_back(u);
        }
        ll ans = 0; 
        vector<int> sz(n, 1), dp(n); // initial subtree sizes and dp[i] = |S_i|
        auto dfs = [&] (auto &dfs, int v, int p) -> void{ // performing DFS in the tree
            for (int u : a[v]) {
                if (u != p) { // to avoid visiting parent again
                    dfs(dfs, u, v); // recursively visit subtree
                    dp[v] += dp[u]; // answer for subtree of v (merge)
                    sz[v] += sz[u]; // merge
                }
            }
            dp[v] += sz[v] >= k;
        };
        dfs(dfs, 0, -1); // arbitrary starting point
        auto reroot = [&] (auto &reroot, int v, int p) -> void{
            for (int u : a[v]) {
                if (u != p) {
                    int add = dp[v] - dp[u] - (n - sz[u] < k); // value of v other than subtree of u
                    dp[u] = add + (dp[u] + (sz[u] < k));  
                    reroot(reroot, u, v); //continue rerooting
                    // Actually you don't need dp[v] for each subtree (because dp[u] cancels out), I did it for clarity. 
                }
            }
        };
        reroot(reroot, 0, -1);
        cout << accumulate(dp.begin(), dp.end(), 0ll) << '\n'; // print the answer
    }
}

Think of longest non-decreasing sequence

In finding simple LNDS, all elements have the same "weights". But here we are given weights.

// author: khba

#include "bits/stdc++.h"
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int64_t a[n], c[n], dp[n];
        for (int64_t &i : a) cin >> i;
        for (int64_t &i : c) cin >> i;
        for (int i = 0; i < n; ++i) dp[i] = c[i];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + c[i]);
        cout << accumulate(c, c + n, 0LL) - *max_element(dp, dp + n) << '\n';
    }
}

Solve for $$$n \le 2 * 10^5$$$