#736282 (C++17) No.898 tri-βutree

提出ソース
結果

問題	No.898 tri-βutree
ユーザー	raven7959
提出日時	2022-02-03 10:06:43
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,953 bytes
コンパイル時間	2,615 ms
コンパイル使用メモリ	222,420 KB
実行使用メモリ	32,528 KB
最終ジャッジ日時	2024-06-11 09:43:38
合計ジャッジ時間	11,284 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	217 ms 32,528 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define yn(joken) cout<<((joken) ? "Yes" : "No")<<endl
#define YN(joken) cout<<((joken) ? "YES" : "NO")<<endl
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvd = vector<vector<double>>;
const int INF = 1e9;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        os << v[i];
        if (i < int(v.size()) - 1) os << ' ';
    }
    return os;
}

template <typename T = int>
struct Edge{
    int from, to;
    T cost;
    int idx;
    Edge() = default;
    Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}
    operator int() const { return to; }
};

template <typename T = int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int es;
    Graph() = default;
    explicit Graph(int n) : g(n), es(0) {}
    size_t size() const{
        return g.size();
    }

    void add_directed_edge(int from, int to, T cost = 1){
        g[from].emplace_back(from, to, cost, es++);
    }

    void add_edge(int from, int to, T cost = 1){
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }

    void read(int M, int padding = -1, bool weighted = false, bool directed = false){
        for (int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
            a += padding;
            b += padding;
            T c = T(1);
            if (weighted) cin >> c;
            if (directed) add_directed_edge(a, b, c);
            else add_edge(a, b, c);
        }
    }

    inline vector<Edge<T>> &operator[](const int &k){
        return g[k];
    }

    inline const vector<Edge<T>> &operator[](const int &k) const{
        return g[k];
    }
};

template <typename T = int>
using Edges = vector<Edge<T>>;

// HeavyLightDecomposition<Graph<int>> HLD(g,root); などする,rootは指定しない場合0になる
// size: 部分木のサイズ(元の木の頂点番号->サイズ)
// depth: 深さ(元の木の頂点番号->深さ)
// down: 行きがけ順(セグ木上での順番でもある) (元の木の頂点番号->行きがけ順)
// up: 部分木クエリに使うやつ
// nxt: ある頂点が属する連結成分の中で最も浅い頂点(元の木の頂点番号->元の木の頂点番号)
// par: 親の番号(元の木の頂点番号->元の木の頂点番号)
// rev: 行きがけ順から元の木の頂点番号に戻す配列
// void path_query(int u,int v,bool vertex,F f): u,vパスについての可換なクエリを処理,頂点属性ならvertexをtrueにする
// void path_noncommutative_query(int u,int v,bool vertex,F f): u,vパスについての非可換なクエリを処理,頂点属性ならvertexをtrueにする
// void subtree_query(int u,bool vertex,F f): uを根とする部分木についてのクエリを処理
// 上3つではいずれもラムダ式でfを渡せばよく,[l,r)についての結果をどこかにまとめる感じで書くと良い
// その他,汎用的な関数がある(lca,la,dist,in_subtree,move)

template <typename G>
struct HeavyLightDecomposition{
private:
    void dfs_sz(int cur){
        size[cur] = 1;
        for (auto &dst : g[cur]){
            if (dst == par[cur]){
                if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]);
                else continue;
            }
            depth[dst] = depth[cur] + 1;
            par[dst] = cur;
            dfs_sz(dst);
            size[cur] += size[dst];
            if (size[dst] > size[g[cur][0]]) swap(dst, g[cur][0]);
        }
    }

    void dfs_hld(int cur){
        down[cur] = id++;
        rev[down[cur]] = cur;
        for (auto dst : g[cur]){
            if (dst == par[cur]) continue;
            nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst));
            dfs_hld(dst);
        }
        up[cur] = id;
    }

    // [u, v)
    vector<pair<int, int>> ascend(int u, int v) const{
        vector<pair<int, int>> res;
        while (nxt[u] != nxt[v]){
            res.emplace_back(down[u], down[nxt[u]]);
            u = par[nxt[u]];
        }
        if (u != v) res.emplace_back(down[u], down[v] + 1);
        return res;
    }

    // (u, v]
    vector<pair<int, int>> descend(int u, int v) const{
        if (u == v) return {};
        if (nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}};
        auto res = descend(u, par[nxt[v]]);
        res.emplace_back(down[nxt[v]], down[v]);
        return res;
    }

public:
    G &g;
    int id;
    vector<int> size, depth, down, up, nxt, par, rev;
    HeavyLightDecomposition(G &_g, int root = 0)
        : g(_g),
          id(0),
          size(g.size(), 0),
          depth(g.size(), 0),
          down(g.size(), -1),
          up(g.size(), -1),
          nxt(g.size(), root),
          par(g.size(), root),
          rev(g.size(), root)
    {
        dfs_sz(root);
        dfs_hld(root);
    }

    void build(int root){
        dfs_sz(root);
        dfs_hld(root);
    }

    pair<int, int> idx(int i) const { return make_pair(down[i], up[i]); }

    template <typename F>
    void path_query(int u, int v, bool vertex, const F &f){
        int l = lca(u, v);
        for (auto &&[a, b] : ascend(u, l)){
            int s = a + 1, t = b;
            s > t ? f(t, s) : f(s, t);
        }
        if (vertex) f(down[l], down[l] + 1);
        for (auto &&[a, b] : descend(l, v)){
            int s = a, t = b + 1;
            s > t ? f(t, s) : f(s, t);
        }
    }

    template <typename F>
    void path_noncommutative_query(int u, int v, bool vertex, const F &f){
        int l = lca(u, v);
        for (auto &&[a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(down[l], down[l] + 1);
        for (auto &&[a, b] : descend(l, v)) f(a, b + 1);
    }

    template <typename F>
    void subtree_query(int u, bool vertex, const F &f){
        f(down[u] + int(!vertex), up[u]);
    }

    int lca(int a, int b){
        while (nxt[a] != nxt[b]){
            if (down[a] < down[b]) swap(a, b);
            a = par[nxt[a]];
        }
        return depth[a] < depth[b] ? a : b;
    }

    int lca(int r, int u, int v){
        return lca(r, u) ^ lca(u, v) ^ lca(v, r);
    }

    int la(int v, int k) {
        while(1){
            int u = nxt[v];
            if(down[v] - k >= down[u]) return rev[down[v] - k];
            k -= down[v] - down[u] + 1;
            v = par[nxt[u]];
        }
    }

    int dist(int a, int b) { return depth[a] + depth[b] - depth[lca(a, b)] * 2; }

    bool in_subtree(int a, int b) { return down[a] <= down[b] && down[b] <= up[a]; }

    int move(int a, int b) {
        assert(a != b);
        return (in_subtree(b, a) ? la(b, depth[b] - depth[a] - 1) : par[a]);
    }
};

// segtree<S,op,e> seg(int n)またはsegtree<S,op,e> seg(vector<S> vec)で初期化
// Sは型, Sを返す関数op(S a,S b)と単位元S e()を設定する
// set(int p,S x): a[p]にxを代入する
// get(int p): a[p]を取得する
// prod(int l,int r): [l,r)をfoldした結果を返す
// all_prod(): [0,n)をfoldした結果を返す
// max_right<f>(int l): bool f(S x)を渡すとl以降でf(prod(l,r))=trueとなる最大のrを返す
// min_left: max_rightの逆

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

template <class S, S (*op)(S, S), S (*e)()>
struct segtree{
public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(vector<S>(n, e())) {}
    segtree(const vector<S> &v) : _n(int(v.size())){
        log = ceil_pow2(_n);
        size = 1 << log;
        d = vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++)
            update(p >> i);
    }

    S get(int p){
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r){
            if (l & 1)
                sml = op(sml, d[l++]);
            if (r & 1)
                smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)>
    int max_right(int l){
        return max_right(l, [](S x)
                         { return f(x); });
    }
    template <class F>
    int max_right(int l, F f){
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do{
            while (l % 2 == 0)
                l >>= 1;
            if (!f(op(sm, d[l]))){
                while (l < size){
                    l = (2 * l);
                    if (f(op(sm, d[l]))){
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)>
    int min_left(int r){
        return min_left(r, [](S x)
                        { return f(x); });
    }
    template <class F>
    int min_left(int r, F f){
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do{
            r--;
            while (r > 1 && (r % 2))
                r >>= 1;
            if (!f(op(d[r], sm))){
                while (r < size){
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))){
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

int op(int l,int r){return l+r;}
int e(){return 0;}

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

    int N;
    cin>>N;
    Graph<ll> G(N);
    vector<tuple<ll,ll,ll>> E;
    rep(_,N-1){
        ll u,v,w;
        cin>>u>>v>>w;
        G.add_edge(u,v,w);
        E.emplace_back(u,v,w);
    }
    HeavyLightDecomposition<Graph<ll>> HLD(G);
    segtree<int,op,e> seg(N);
    for(auto [u,v,w]:E){
        seg.set(max(HLD.down[u],HLD.down[v]),w);
    }
    int Q;
    cin>>Q;
    rep(_,Q){
        int x,y,z;
        cin>>x>>y>>z;
        ll ans=0;
        auto f=[&](int l,int r)->void{
            ans+=seg.prod(l,r);
        };
        HLD.path_query(x,y,false,f);
        HLD.path_query(y,z,false,f);
        HLD.path_query(z,x,false,f);
        cout<<ans/2<<endl;
    }
}
yukicoder

結果

テストケース

ソースコード
