LC361T4

using a26i = array<int, 27>;
class Solution {
    constexpr static int log = 15;
    struct Edge {
        int v, w, next;
    } es[20003];
    int ecnt = 0;
    int head[10003];
    void init() {
        memset(head, -1, sizeof(head));
        ecnt = 0;
    }
    void insert(int u, int v, int w) {
        es[ecnt] = {v, w, head[u]};
        head[u] = ecnt++;

        es[ecnt] = {u, w, head[v]};
        head[v] = ecnt++;
    }
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& qs) {
        a26i val;
        for (auto&x:val) x = 0;
        vector<vector<a26i>> dp(n + 1, vector<a26i>(log, val));
        vector<vector<int>> pa(n + 1, vector<int>(log));
        vector<int> dep(n + 1);
        init();
        for (auto& e: edges) {
            int u = e[0], v = e[1], w = e[2];
            insert(u, v, w);
        }
        function<void(int, int, int)> dfs = [&](int u, int fa, int depth) {
            dep[u] = depth;
            for (int eid = head[u]; eid != -1; eid = es[eid].next) {
                int w = es[eid].w, v = es[eid].v;
                if (v == fa) continue;
                dp[v][0][w] += 1;
                pa[v][0] = u;
                dfs(v, u, depth + 1);
            }
        };
        dfs(0, -1, 0);
        for (int i = 1; i < log; ++i) {
            for (int u = 0; u < n; ++u) {
                pa[u][i] = pa[pa[u][i-1]][i-1];
                a26i curr = dp[u][i-1];
                for (int j = 0; j <= 26; ++j)
                    curr[j] += dp[pa[u][i-1]][i-1][j], assert(curr[j] >= 0);
                dp[u][i] = curr;
            }
        }

        function<int(int, int)> lca = [&](int u, int v) {
            if (dep[u] < dep[v]) swap(u, v);
            a26i cnt = val;
            for (int st = log - 1; st >= 0; --st) {
                if (dep[pa[u][st]] >= dep[v]) {
                    for (int i = 0; i <= 26; ++i)
                        cnt[i] += dp[u][st][i], assert(cnt[i] >= 0);
                    u = pa[u][st];
                }
            }
            if (u != v) {
                for (int st = log - 1; st >= 0; --st) {
                    if (pa[u][st] != pa[v][st]) {
                        for (int i = 0; i <= 26; ++i)
                            cnt[i] += dp[u][st][i] + dp[v][st][i], assert(cnt[i] >= 0);
                        u = pa[u][st], v = pa[v][st];
                    }
                }
                for (int i = 0; i <= 26; ++i)
                    cnt[i] += dp[u][0][i] + dp[v][0][i];
            }

            int sum = 0;
            for (int i = 0; i <= 26; ++i) sum += cnt[i];
            // cout << "sum: " << sum << endl;
            int ret = INT_MAX;
            for (int i = 0; i <= 26; ++i) ret = min(ret, sum - cnt[i]);
            return ret;
        };

        vector<int> ans;
        for (auto q: qs) {
            int u = q[0], v = q[1];
            ans.push_back(lca(u, v));
        }
        return ans;
    }
};