#117941 (C++11（廃止可能性あり）) No.650 行列木クエリ

• 問題: No.650 行列木クエリ
• ユーザー: はむこ
• 提出日時: 2016-09-19 23:19:09
• 言語: C++11（廃止可能性あり） (gcc 13.3.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 10,557 bytes
• コンパイル時間: 2,267 ms
• コンパイル使用メモリ: 194,580 KB
• 実行使用メモリ: 35,144 KB
• 最終ジャッジ日時: 2024-07-18 01:24:03
• 合計ジャッジ時間: 6,698 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 1
other	AC * 7 TLE * 1 -- * 2

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define Min(x) *min_element(all(x))
#define Max(x) *max_element(all(x))
template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { if (!v.empty()) { o << '['; copy(v.begin(), v.end(), ostream_iterator<T>(o, ", ")); o << "\b\b]"; } return o; }
using ll = long long; using ld = long double; using vll = vector<ll>; using vi = vector<int>;
typedef pair<ld, ld> P;

static const double EPS = 1e-14;
static const long long INF = 1e18;
#define MAX_N 100005

class Mod {
    public:
        int num;
        int mod;
        Mod() : Mod(0) {}
        Mod(long long int n) : Mod(n, 1000000007) {}
        Mod(long long int n, int m) { mod = m; num = (n % mod + mod) % mod;}
        Mod(const string &s){ long long int tmp = 0; for(auto &c:s) tmp = (c-'0'+tmp*10) % mod; num = tmp; }
        Mod(int n) : Mod(static_cast<long long int>(n)) {}
        operator int() { return num; }
        void setmod(const int mod) { this->mod = mod; }
};
istream &operator>>(istream &is, Mod &x) { long long int n; is >> n; x = n; return is; }
ostream &operator<<(ostream &o, const Mod &x) { o << x.num; return o; }
Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % a.mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((a.mod + a.num - b.num) % a.mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % a.mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod factorial(const long long n) {
    if (n < 0) return 0;
    Mod ret = 1;
    for (int i = 1; i <= n; i++) {
        ret *= i;
    }
    return ret;
}
Mod operator^(const Mod a, const long long n) {
    if (n == 0) return Mod(1);
    Mod res = (a * a) ^ (n / 2);
    if (n % 2) res = res * a;
    return res;
}
Mod modpowsum(const Mod a, const long long b) {
    if (b == 0) return 0;
    if (b % 2 == 1) return modpowsum(a, b - 1) * a + Mod(1);
    Mod result = modpowsum(a, b / 2);
    return result * (a ^ (b / 2)) + result;
}

/*************************************/
// GF(p)の行列演算
/*************************************/
using number = Mod;
using arr = vector<number>;
using matrix = vector<vector<Mod>>;

ostream &operator<<(ostream &o, const arr &v) { rep(i, v.size()) cout << v[i] << " "; cout << endl; return o; }
ostream &operator<<(ostream &o, const matrix &v) { rep(i, v.size()) cout << v[i]; return o; }

matrix zero(int n) { matrix A(n, arr(n, 0)); return A; } // O(n^2)
matrix identity(int n) { matrix A(n, arr(n, 0)); rep(i, n) A[i][i] = 1; return A; } // O(n^2)

// O(n^3)
matrix mul(const matrix &A, const matrix &B) {
    matrix C(A.size(), arr(B[0].size(), 0));
    rep(i, C.size())
        rep(j, C[i].size())
        rep(k, A[i].size())
        C[i][j] += A[i][k] * B[k][j];
    return C;
}
// O(n^2)
matrix plu(const matrix &A, const matrix &B) {
    matrix C(A.size(), arr(B[0].size(), 0));
    rep(i, C.size())
        rep(j, C[i].size())
            C[i][j] += A[i][j] + B[i][j];
    return C;
}

// 静的木
//
// 構築O(n): オイラーツアー, 木の高さ, 祖先ダブリング
//
// LCA O(log n)
// 頂点間最小辺数 O(log n)
// 頂点から根までのパスの二分探索 O(log n)
struct edge_t { int from, to; ll weight; };
using verticle_t = ll;
class Tree {
public:
    int MAXLOGV;
    vector<vector<edge_t>> m_edges; // m_edges[i][j]が存在: i->jの辺が存在
    int vn; // 頂点の数, vn<2^MAXLOGV
    int root; // 根ノードの番号

    vector<verticle_t> m_verticles; 
    vector<vector<verticle_t>> m_verticles_doubling; // m_verticles_doubling[i][j]: jのi^2番目の親までのm_vertivlesの結合演算opによる積分

    vector<vector<int>> parent; // parent[i][j]: jのi^2番目の親。j=0で直近の親。
    vector<int> depth; // depth[i]: 頂点iの根からの深さ, 根が0


    /*********/
    // 構築
    /*********/
    Tree(int vn, int root) : vn(vn), root(root) {
        // TODO このへんの確保を最低限に
        MAXLOGV = ceil(log(vn) / log(2)) + 2; // +2は念の為
        m_edges.resize(vn);
        m_verticles.resize(vn);
        parent.resize(MAXLOGV); rep(i, MAXLOGV) parent[i].resize(vn);
        depth.resize(vn);
    }

    // 辺の構築
    void unite(edge_t e) {
        m_edges[e.from].push_back({e.from, e.to, e.weight});
        m_edges[e.to].push_back({e.to, e.from, e.weight});
    }
    void unite(int u, int v) {
        unite({u, v, 1});
    }

    // 頂点の構築
    void setVerticle(int i, verticle_t v) {
        m_verticles_doubling[0][i] = m_verticles[i] = v;
    }

    // rootからの深さと親を確認。
    // uniteし終わったらまずこれを呼ぶこと。
    void init() {
        dfs(root, -1, 0);
        for (int k = 0; k+1 < MAXLOGV; k++) // 2^k代祖先を計算
            for (int v = 0; v < vn; v++) 
                if (parent[k][v] < 0) 
                    parent[k+1][v] = -1; // 2^k代親が根を超えてるなら、2^(k+1)代親も根を超える
                else 
                    parent[k+1][v] = parent[k][parent[k][v]]; // 2^(k+1)代の親は、2^k代親の2^k代親

        // 親のダブリング
        rep(k, MAXLOGV - 1) // 2^k代祖先を計算
            for (int v = 0; v < vn; v++) 
                if (parent[k][v] < 0) 
                    parent[k+1][v] = -1; // 2^k代親が根を超えてるなら、2^(k+1)代親も根を超える
                else 
                    parent[k+1][v] = parent[k][parent[k][v]]; // 2^(k+1)代の親は、2^k代親の2^k代親

    }

    // 1つ親と深さとオイラーツアーを構築
    // TODO 機能毎に分ける
    void dfs(int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (edge_t next : m_edges[v]) 
            if (next.to != p)
                dfs(next.to, v, d+1);
    }

    // 木の直径を求める
    // 辺が重み付きでもOK!
    //
    // O(V)
    ll diameter(void) {
        using Result = pair<ll, int>;
        function<Result(int, int)> visit = [&](int p, int v){ 
            Result r(0, v);
            for (auto e : m_edges[v]) if (e.to != p) {
                Result t = visit(v, e.to);
                t.first += e.weight;
                if (r.first < t.first) r = t;
            }
            return r;
        };

        Result r = visit(-1, 0);
        Result t = visit(-1, r.second);

        // このあと、r, tからの距離を使って木の中心を求めることができる。O(V)
        // t.firstが偶数なら、rからt.first/2かつtからt.first/2の距離
        // t.firstが偶数なら、rからt.first/2+1or+0かつtからt.first/2+1or+0の距離の二点
        
        return t.first; // (r.second, t.second) is farthest pair
    }

    /*************/
    // 頂点クエリ
    /*************/
    // 頂点u, vの最小共通先祖
    //
    // O(log n)
    int getParent(int index, ll n) const {
        ll ret = index;
        n = min(n, (1ll << MAXLOGV) - 1);
        rep(k, MAXLOGV) if (ret != -1) if (n & (1ll << k)) {
            ret = parent[k][ret];
        }
        return ret;
    }

    // 頂点u, vの最小共通先祖
    //
    // O(log n)
    int lca(int u, int v) const {
        if (depth[u] > depth[v]) swap(u, v); // uのほうが浅くなるように
        for (int k = 0; k < MAXLOGV; k++)    // vをuと同じ深さまで遡る
            if ((depth[v] - depth[u])>>k & 1) 
                v = parent[k][v];
        if (u == v) return u;
        for (int k = MAXLOGV-1; k >= 0; k--) { // 行き過ぎないギリギリで遡る
            if (parent[k][u] == parent[k][v]) // 行き過ぎ
                continue; 
            u = parent[k][u];
            v = parent[k][v];
        }
        return parent[0][u];
    }

    // uとvの距離を求める
    // 距離はエッジの重み=1としたときのもの
    //
    // O(log n)
    int dist(int u, int v) const {
        int p = lca(u, v);
        return (depth[u]-depth[p]) + (depth[v]-depth[p]);
    }


    /*************/
    // 描画
    /*************/
    void print_dfs(int v, int p) const {
        for (int i = 0; i < depth[v]; i++)
            cout << " ";
        cout << v << endl;
        for (edge_t next : m_edges[v]) if (next.to != p) 
            print_dfs(next.to, v);
    }
    void print(void) const {
        print_dfs(root, -1);
    }
};

int main(void) {
    int n; cin >> n;
    Tree tree(n, 0);

    vector<int> as, bs;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        tree.unite(a, b);
        as.pb(a);
        bs.pb(b);
    }
//    tree.print();
    tree.init();

    vector<matrix> data(n, identity(2));
    

    ll q; cin >> q;
    rep(_, q) {
        char c; cin >> c;
        if (c == 'x') {
            ll index; cin >> index;
            int leaf_side_index = (tree.depth[as[index]] > tree.depth[bs[index]] ? as[index] : bs[index]);
            matrix m = zero(2);
            cin >> m[0][0] >> m[0][1] >> m[1][0] >> m[1][1];
            data[leaf_side_index] = m;
        } else {
            ll u, v; cin >> u >> v; // u is root size
            matrix m = identity(2);
            while (u != v) {
                m = mul(data[v], m);
                v = tree.getParent(v, 1);
            }
            cout << m[0][0] << " " << m[0][1] << " " << m[1][0] << " " << m[1][1] << endl;
        }
    }
    return 0;
}