結果

問題 No.650 行列木クエリ
ユーザー みやべ
提出日時 2025-10-11 21:23:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 4,318 bytes
コンパイル時間 2,133 ms
コンパイル使用メモリ 218,088 KB
実行使用メモリ 39,424 KB
最終ジャッジ日時 2025-10-11 21:23:08
合計ジャッジ時間 4,334 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
#include <atcoder/segtree>
using mint = atcoder::modint1000000007;

template<typename S, S(*op)(S, S), S(*e)()>
struct HLD {
    using seg_t = atcoder::segtree<S, op, e>;
    
    int n;
    vector<int> dep, in, out, head, par;
    vector<pair<array<int, 2>, S>> E;
    seg_t node[2];
    
    HLD(int _n) : n(_n), dep(n), in(n), out(n), head(n), par(n) {}
    
    void add_edge(int u, int v, const S &x){
        E.push_back({{u, v}, x});
    }
    
    void build(){
        vector<vector<pair<int, S>>> G(n);
        for(auto i : E){
            G[i.first[0]].push_back({i.first[1], i.second});
            G[i.first[1]].push_back({i.first[0], i.second});
        }
        
        vector<int> sub_siz(n, 1);
        
        par[0] = -1;
        auto f1 = [&](auto self, int pos)->void {
            for(int i = 0; i < (int)G[pos].size(); i++){
                int nex = G[pos][i].first;
                if(nex == par[pos]) continue;
                par[nex] = pos;
                self(self, nex);
                sub_siz[pos] += sub_siz[nex];
            }
        }; f1(f1, 0);
        
        int cnt = 0;
        auto f2 = [&](auto self, int pos)->void {
            in[pos] = cnt++;
            if(sub_siz[pos] == 1){
                out[pos] = cnt;
                return;
            }
            int hv = -1;
            for(int i = 0; i < (int)G[pos].size(); i++){
                int nex = G[pos][i].first;
                if(nex == par[pos]) continue;
                if(hv == -1 || sub_siz[hv] < sub_siz[nex]) hv = nex;
            }
            dep[hv] = dep[pos];
            head[hv] = head[pos];
            self(self, hv);
            for(int i = 0; i < (int)G[pos].size(); i++){
                int nex = G[pos][i].first;
                if(nex == par[pos] || nex == hv) continue;
                dep[nex] = dep[pos]+1;
                head[nex] = nex;
                self(self, nex);
            }
            out[pos] = cnt;
        }; f2(f2, 0);
        
        vector<S> node_v(n, e());
        for(int i = 0; i < n; i++){
            for(int j = 0; j < (int)G[i].size(); j++){
                if(G[i][j].first == par[i]){
                    node_v[in[i]] = G[i][j].second;
                }
            }
        }
        
        node[0] = seg_t(node_v);
        reverse(node_v.begin(), node_v.end());
        node[1] = seg_t(node_v);
    }
    
    S prod(int l, int r){
        S l_ans = e(), r_ans = e();
        while(true){
            if(dep[l] >= dep[r] && head[l] != head[r]){
                l_ans = op(l_ans, node[1].prod(n-in[l]-1, n-in[head[l]]));
                l = par[head[l]];
            } else if(dep[l] < dep[r]){
                r_ans = op(node[0].prod(in[head[r]], in[r]+1), r_ans);
                r = par[head[r]];
            } else {
                if(in[l] <= in[r]) l_ans = op(l_ans, node[0].prod(in[l]+1, in[r]+1));
                else r_ans = op(node[1].prod(n-in[l]-1, n-in[r]-1), r_ans);
                return op(l_ans, r_ans);
            }
        }
    }
    
    S prod(int r){
        return node[0].prod(in[r]+1, out[r]);
    }
    
    S get(int u, int v){
        int p = par[u] == v ? u : v;
        return node[0].get(in[p]);
    }
    
    void set(int u, int v, const S &x){
        int p = par[u] == v ? u : v;
        node[0].set(in[p], x);
        node[1].set(n-in[p]-1, x);
    }
};


using S = array<mint, 4>;
S op(S l, S r) {return {l[0]*r[0]+l[1]*r[2], l[0]*r[1]+l[1]*r[3], l[2]*r[0]+l[3]*r[2], l[2]*r[1]+l[3]*r[3]};}
S e() {return S{1, 0, 0, 1};}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    
    int n;
    cin >> n;
    HLD<S, op, e> seg(n);
    
    vector<array<int, 2>> E(n-1);
    for(int i = 0; i < n-1; i++){
        int u, v;
        cin >> u >> v;
        seg.add_edge(u, v, e());
        E[i] = {u, v};
    }
    
    seg.build();
    
    int q;
    cin >> q;
    while(q--){
        char t;
        cin >> t;
        if(t == 'x'){
            int i, a, b, c, d;
            cin >> i >> a >> b >> c >> d;
            seg.set(E[i][0], E[i][1], S{a, b, c, d});
        } else {
            int u, v;
            cin >> u >> v;
            for(auto i : seg.prod(u, v)) cout << i.val() << ' ';
            cout << '\n';
        }
    }
}
0