結果

問題 No.650 行列木クエリ
コンテスト
ユーザー はまやんはまやん
提出日時 2018-02-10 01:57:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 7,545 bytes
コンパイル時間 2,681 ms
コンパイル使用メモリ 197,088 KB
実行使用メモリ 30,208 KB
最終ジャッジ日時 2024-10-09 10:44:24
合計ジャッジ時間 3,922 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
// vid : id -> vid          head, heavy, parent : unknown
// depth : id -> depth      inv : vid -> id
struct HLDecomposition {
    vector<set<int>> g; vector<int> vid, head, heavy, parent, depth, inv;
    HLDecomposition() {} HLDecomposition(int n) { init(n); }
    void init(int n) { g.resize(n);vid.resize(n, -1);head.resize(n);heavy.resize(n, -1);
        parent.resize(n);depth.resize(n);inv.resize(n);}
    void add(int u, int v) { g[u].insert(v); g[v].insert(u); } void build() { dfs(0, -1); bfs(); }
    int dfs(int curr, int prev) { parent[curr] = prev; int sub = 1, max_sub = 0;
        for (int next : g[curr]) if (next != prev) { depth[next] = depth[curr] + 1;
        int sub_next = dfs(next, curr); sub += sub_next;
        if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next; }return sub;}
    void bfs() { int k = 0; queue<int> q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop();
        for (int i = h; i != -1; i = heavy[i]) {vid[i] = k++; inv[vid[i]] = i; head[i] = h;
        for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);}}}
    void foreach(int u, int v, function<void(int, int)> f) { // [x,y]
        if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]);
        if (head[u] != head[v]) foreach(u, parent[head[v]], f);}
    int ancestor(int from, int times) { while (true) { if (depth[head[from]] > depth[from] - times) {
        times-=depth[from]-depth[head[from]]+1;if(head[from]==0)return -1;from=parent[head[from]];}
        else return inv[vid[from] - times];} }
    int lca(int u, int v) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u;
        return lca(u, parent[head[v]]); }
    int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
    int child(int parent,int child,int times){assert(depth[parent]<depth[child]);
        int d=distance(parent, child);assert(times - 1 <= d);return ancestor(child, d - times);}
    int go(int from,int to,int times){int d=distance(from,to);assert(0<=times and times<=d);
        int lc=lca(from,to);if(lc==to)return ancestor(from,times);if(lc==from)return child(from,to,times);
        int dd=distance(from,lc);if(dd<=times)return go(lc,to,times-dd);return ancestor(from,times);}};
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;
struct func {
    mint x00, x01, x10, x11;
    func(mint a = 1, mint b = 0, mint c = 0, mint d = 1) : x00(a), x01(b), x10(c), x11(d) {}
};
func operator*(func x, func y) {
    mint a = x.x00 * y.x00 + x.x01 * y.x10;
    mint b = x.x00 * y.x01 + x.x01 * y.x11;
    mint c = x.x10 * y.x00 + x.x11 * y.x10;
    mint d = x.x10 * y.x01 + x.x11 * y.x11;
    return func(a, b, c, d);
}
//---------------------------------------------------------------------------------------------------
template<class V, int NV> struct SegTree { // [L,R)
    V comp(V l, V r) { return l * r; };
    vector<V> val; SegTree() { val = vector<V>(NV * 2); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if(r<=x||y<=l)return V();if(x<=l&&r<=y)return val[k];auto A=get(x,y,l,(l+r)/2,k*2);
        auto B = get(x,y,(l+r)/2,r,k*2+1);return comp(A,B);}
    void update(int i, V v){i+=NV;val[i]=v;while (i>1)i>>=1,val[i]=comp(val[i*2],val[i*2+1]);}};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





int N, Q, A[101010], B[101010];
int f[101010];
SegTree<func, 1 << 17> st;
HLDecomposition hld;
func ans; int pre;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    hld.init(N);

    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        A[i] = a; B[i] = b;
        hld.add(a, b);
    }
    hld.build();

    rep(i, 0, N - 1) {
        if (hld.depth[A[i]] < hld.depth[B[i]]) f[i] = B[i];
        else f[i] = A[i];
    }

    cin >> Q;
    rep(q, 0, Q) {
        string t; cin >> t;
        if (t == "x") {
            int i, a, b, c, d;
            cin >> i >> a >> b >> c >> d;
            i = f[i];
            st.update(hld.vid[i], func(a, b, c, d));
        } else {
            int i, j; cin >> i >> j;

            i = hld.go(i, j, 1);

            ans = func();
            pre = -1;
            hld.foreach(j, i, [](int u, int v) {
                int uu = hld.inv[u];
                if (pre < hld.depth[uu]) {
                    ans = ans * st.get(u, v + 1);
                }
                else {
                    ans = st.get(u, v + 1) * ans;
                }

                //rep(x, u, v + 1) printf("[%d] ", x);
                pre = hld.depth[uu];
            });
            //printf("\n");

            printf("%d %d %d %d\n", ans.x00.get(), ans.x01.get(), ans.x10.get(), ans.x11.get());
        }
    }

    //rep(i, 0, N) printf("%d -vid-> %d\n", i, hld.vid[i]);
}
0