题目：https://codeforces.com/contest/1997

A. Strong Password

#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(3, "Ofast", "inline") // O3优化
#define endl "\n"
#define ll long long

char getChar(char before)
{
    char i = 'a';
    for (; i == before; i++)
        ;
    return i;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        string s;
        cin >> s;
        for (int i = 0; i <= s.length() - 1; i++) {
            if (i == s.length() - 1) {
                s.append(1, getChar(s[i]));
                break;
            } else {
                if (s[i] == s[i + 1]) {
                    s.insert(i + 1, 1, getChar(s[i]));
                    break;
                }
            }
        }
        cout << s << endl;
    }

    return 0;
}

B. Make Three Regions

#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(3, "Ofast", "inline") // O3优化
#define endl "\n"
#define ll long long

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s[2];
        cin >> s[0] >> s[1];
        int cnt = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (s[i][n == '.']) {
                    if (s[(i + 1) % 2][j - 1] == 'x' && s[(i + 1) % 2][j + 1] == 'x' && s[(i + 1) % 2][j] == '.' && s[i][j - 1] == '.' && s[i][j + 1] == '.') {
                        cnt++;
                    }
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

C. Even Positions

#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(3, "Ofast", "inline") // O3优化
#define endl "\n"
#define ll long long

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        int cnt_l = 0;
        ll step = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '_') {
                if (cnt_l > 0) {
                    cnt_l--;
                } else {
                    cnt_l++;
                }
            } else {
                if (s[i] == '(') {
                    cnt_l++;
                } else {
                    cnt_l--;
                }
            }
            step += cnt_l;
        }
        cout << step << endl;
    }

    return 0;
}

D. Maximize the Root

#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(3, "Ofast", "inline") // O3优化
#define endl "\n"
#define ll long long

const int N = 2e5 + 5;

struct Node {
    int value;
    int parent;
    vector<int> sons;
};

Node tree[N];

ll postorder(int ind)
{
    if (tree[ind].sons.empty()) {
        return tree[ind].value;
    }

    ll sonsMin = INFINITY;
    for (auto&& i : tree[ind].sons) {
        sonsMin = min(postorder(i), sonsMin);
    }

    if (ind == 1) {
        return sonsMin;
    }

    if (sonsMin <= tree[ind].value) {
        return sonsMin;
    } else {
        return (sonsMin + tree[ind].value) >> 1;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        memset(tree, 0, sizeof(tree));
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> tree[i].value;
        }
        for (int i = 2; i <= n; i++) {
            int parent;
            cin >> parent;
            tree[i].parent = parent;
            tree[parent].sons.push_back(i);
        }

        cout << tree[1].value + postorder(1) << endl;
    }

    return 0;
}