#1193091 (C++23) No.898 tri-βutree

• 問題: No.898 tri-βutree
• ユーザー: Today03
• 提出日時: 2026-10-14 19:55:34
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: RE
• 実行時間: -
• コード長: 3,033 bytes
• コンパイル時間: 1,907 ms
• コンパイル使用メモリ: 225,828 KB
• 実行使用メモリ: 9,984 KB
• 最終ジャッジ日時: 2026-10-14 19:57:01
• 合計ジャッジ時間: 9,897 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	RE * 1
other	RE * 21

コンパイルメッセージ

main.cpp:20:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
   20 | #pragma once
      |         ^~~~

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <numeric>
using namespace std;
using ii = long long;
using ll = long long;
#define rep(i, N) for(ii i = 0; i < (N); i++)
#define all(v) (v).begin(), (v).end()
void chmin(auto& a, auto b) { a = (a < b ? a : b); }
void chmax(auto& a, auto b) { a = (a > b ? a : b); }
const ii INF = 1e9 + 10;
const ll INFL = 4e18;

// https://yukicoder.me/problems/no/898

#pragma once
#include <vector>
#include <algorithm>
#include <bit>
using namespace std;

struct LCA {
    int lg;
    vector<vector<int>> par;
    vector<int> dep;
    vector<ll> wei;
    LCA(const vector<vector<pair<int, ll>>>& g, int root = 0) {
        int n = g.size();
        lg = bit_width((unsigned)n);
        par.assign(lg, vector<int>(n, root));
        dep.assign(n, 0);
        wei.assign(n, 0);
        auto dfs = [&](auto self, int v, int p) -> void {
            par[0][v] = p;
            for(auto [u, w] : g[v])
                if(u != p) {
                    dep[u] = dep[v] + 1;
                    wei[u] = wei[v] + w;
                    self(self, u, v);
                }
        };
        dfs(dfs, root, root);
        for(int j = 1; j < lg; j++)
            for(int v = 0; v < n; v++) par[j][v] = par[j - 1][par[j - 1][v]];
    }
    int lca(int u, int v) {
        if(dep[u] < dep[v]) swap(u, v);
        int k = dep[u] - dep[v];
        for(int j = 0; j < lg; j++)
            if(k >> j & 1) u = par[j][u];
        if(u == v) return u;
        for(int j = lg - 1; j >= 0; j--)
            if(par[j][u] != par[j][v]) u = par[j][u], v = par[j][v];
        return par[0][u];
    }
    ll weight(int u, int v) { return wei[u] + wei[v] - 2 * wei[lca(u, v)]; }
    int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
};

void run() {
    int N;
    cin >> N;
    vector<vector<pair<int, ll>>> G(N);
    rep(i, N - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    LCA lca(G);
    int Q;
    cin >> Q;
    while(Q--) {
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;
        z--;
        vector<int> st;
        st.push_back(lca.lca(x, y));
        st.push_back(lca.lca(y, z));
        st.push_back(lca.lca(z, x));
        sort(all(st));
        st.erase(unique(all(st)), st.end());
        sort(all(st), [&](ii l, ii r) { return lca.dep[l] < lca.dep[r]; });
        ii top = st[0];

        ll ans = 0;
        ans += lca.weight(top, x);
        ans += lca.weight(top, y);
        ans += lca.weight(top, z);
        if(lca.lca(x, y) != top) ans -= lca.weight(top, lca.lca(x, y));
        if(lca.lca(y, z) != top) ans -= lca.weight(top, lca.lca(y, z));
        if(lca.lca(z, x) != top) ans -= lca.weight(top, lca.lca(z, x));

        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    while(T--) run();
}