class Solution {
public:
    int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for (int i = low; i <= high; i++) {
            string s = to_string(i);
            int n = s.size();
            if (n % 2 == 0) {
                int sum1 = 0, sum2 = 0;
                for (int i = 0; i < n / 2; i++) {
                    sum1 += s[i] - '0';
                }
                for (int i = n / 2; i < n; i++) {
                    sum2 += s[i] - '0';
                }
                if (sum1 == sum2) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int minimumOperations(string num) {
        int n = num.size();
        vector<string> arr = {"00", "25", "50", "75"};
        int ans = n;
        auto calc = [&](string s) {
            int count = 0;
            for (int i = s.size() - 1, j = n - 1; i >= 0; i--) {
                while (j >= 0 && num[j] != s[i]) {
                    j--;
                    count++;
                }
                if (j < 0) {
                    return -1;
                }
                if (num[j] == s[i]) {
                    j--;
                }
            }
            return count;
        };
        
        for (int i = 0; i < 4; i++) {
            int cnt = calc(arr[i]);
            if (cnt >= 0) {
                ans = min(ans, cnt);
            }
        }
        
        /* zero */
        for (int i = 0; i < n; i++) {
            if (num[i] == '0') {
                ans = min(ans, n - 1);
            }
        }
        return ans;
    }
};

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        int n = nums.size();
        vector<int> sum(n + 1);
        for (int i = 0; i < n; i++) {
            if (nums[i] % modulo == k) {
                sum[i + 1] = sum[i] + 1;
            } else {
                sum[i + 1] = sum[i];
            }
        }
        unordered_map<int, int> cnt;
        long long res = 0;
        cnt[0] = 1;
        for (int i = 0; i < n; i++) {
            int x = sum[i + 1];
            int y = x % modulo;
            res += cnt[(y + modulo - k) % modulo];
            cnt[sum[i + 1] % modulo]++;
        }
        return res;
    }
};

class Solution {
public:
    using pii = pair<int, int>;

    void bfs(vector<int> &depth, vector<vector<pii>> &graph) {
        depth[0] = 0;
        queue<int> qu;
        qu.emplace(0);
        while (!qu.empty()) {
            int curr = qu.front();
            qu.pop();
            for (auto [x, w] : graph[curr]) {
                if (depth[x] >= 0) continue;
                depth[x] = depth[curr] + 1;
                qu.emplace(x);
            }
        }
    }

    void add(vector<int> &arr1, vector<int> &arr2) {
        for (int i = 0; i < arr1.size(); i++) {
            arr1[i] += arr2[i];
        }
    }

    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        int m = edges.size();
        vector<vector<pii>> graph(n);
        /* 建立图的关系 */
        for (auto e : edges) {
            int u = e[0], v = e[1], w = e[2];
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        }

        vector<int> res;
        vector<int> depth(n, -1);
        int dp[n][21][27];
        int fa[n][21];
        memset(dp, 0, sizeof(dp));
        memset(fa, 0, sizeof(fa));

        /* 求每个节点的深度， bfs 或者 dfs 均可*/
        bfs(depth, graph);

        /* 倍增初始化 */
        for (auto e : edges) {
            int u = e[0], v = e[1], w = e[2];
            /* 深度较小的父节点 */
            if (depth[u] < depth[v]) {
                swap(u, v);
            }
            fa[u][0] = v;
            dp[u][0][w]++;
        }

        /* 建立倍增关系 */
        for (int j = 1; j <= 20; j++) {
            for (int i = 0; i < n; i++) {
                int x = fa[i][j - 1];
                int y = fa[x][j - 1];
                fa[i][j] = y;
                /* 每次记录两个节点之间的节点数目关系 */
                for (int k = 0; k <= 26; k++) {
                    dp[i][j][k] = dp[i][j - 1][k] + dp[x][j - 1][k];
                }
            }
        }
        
        /* 对每个查询进行 lca 倍增查询 */
        for (auto vec : queries) {
            int x = vec[0];
            int y = vec[1];
            if (depth[x] > depth[y]) {
                swap(x, y);
            }

            /* 倍增对齐操作 */
            int diff = depth[y] - depth[x];
            vector<int> cnt(27);
            for (int j = 0; diff; ++j, diff >>= 1) {
                if (diff & 1) {
                    for (int k = 0; k <= 26; k++) {
                        cnt[k] += dp[y][j][k];
                    }
                    y = fa[y][j];
                }
            }
            
            if (x != y) {
                /* 倍增查询 */
                for (int j = 20; j >= 0 && y != x; --j) {
                    if (fa[x][j] != fa[y][j]) {
                        for(int k = 0; k <= 26; k++) {
                            cnt[k] += dp[x][j][k] + dp[y][j][k];
                        }
                        x = fa[x][j];
                        y = fa[y][j];
                    }
                }
                for (int k = 0; k <= 26 && x >= 0 && y >= 0; k++) {
                    cnt[k] += dp[x][0][k] + dp[y][0][k];
                }
            }
             int total = accumulate(cnt.begin(), cnt.end(), 0);
             int maxVal = *max_element(cnt.begin(), cnt.end());
             res.emplace_back(total - maxVal);
        }
        return res;
    }
};