結果

問題 No.650 行列木クエリ
ユーザー nebukuro09nebukuro09
提出日時 2018-03-02 14:03:43
言語 D
(dmd 2.106.1)
結果
WA  
実行時間 -
コード長 5,065 bytes
コンパイル時間 1,019 ms
コンパイル使用メモリ 151,540 KB
実行使用メモリ 600,596 KB
最終ジャッジ日時 2024-06-12 23:58:37
合計ジャッジ時間 4,695 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 MLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.datetime;

alias Mat = Tuple!(long, "a", long, "b", long, "c", long, "d");
immutable long MOD = 10^^9 + 7;
immutable Mat E = Mat(1L, 0L, 0L, 1L);

Mat mul(Mat X, Mat Y) {
    auto ret =  Mat(X.a * Y.a + X.b * Y.c, X.a * Y.b + X.b * Y.d,
                    X.c * Y.a + X.d * Y.c, X.c * Y.b + X.d * Y.d);
    return Mat(ret.a % MOD, ret.b % MOD,
               ret.c % MOD, ret.d % MOD);
}

class HLDecomposition {
    alias Node = Tuple!(int, "group", int, "number");
    
    int N;
    int[][] G;
    int[][] groups;
    int[] group_parent;
    Node[] nodes;

    this (int N) {
        this.N = N;
        G = new int[][](N);
        nodes = new Node[](N);
    }

    void add_edge(int u, int v) {
        G[u] ~= v;
    }

    void run(int root) {
        auto subtree_size = dfs_subtree_size(root);
        int group_count = -1;

        void decompose(int n, int p, bool heavy) {
            if (!heavy) {
                group_count += 1;
                groups.length += 1;
                group_parent ~= p;
            }

            nodes[n] = Node(group_count, groups[group_count].length.to!int);
            groups[group_count] ~= n;

            bool first = true;
            G[n].sort!((a, b) => subtree_size[a] > subtree_size[b]);
            
            foreach (m; G[n]) {
                if (m == p) continue;
                decompose(m, n, first);
                first = false;
            }
        }

        decompose(root, -1, false);
        group_count += 1;
    }

    int[] dfs_subtree_size(int root) {
        auto subtree_size = new int[](N);

        int dfs(int n, int p) {
            subtree_size[n] = 1;
            foreach (m; G[n]) if (m != p) subtree_size[n] += dfs(m, n);
            return subtree_size[n];
        }

        dfs(root, -1);
        return subtree_size;
    }
}


class SegmentTree {
    Mat[] table;
    int size;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new Mat[](size);
        table.fill(E);
    }

    void assign(int pos, Mat X) {
        return assign(pos, X, 0, 0, size/2-1);
    }

    void assign(int pos, Mat X, int i, int left, int right) {
        if (left == right) {
            table[i] = X;
            return;
        }
        
        auto mid = (left + right) / 2;
        if (pos <= mid)
            assign(pos, X, i*2+1, left, mid);
        else
            assign(pos, X, i*2+2, mid+1, right);

        table[i] = mul(table[i*2+1], table[i*2+2]);
    }

    Mat sum(int pl, int pr) {
        return sum(pl, pr, 0, 0, size/2-1);
    }

    Mat sum(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return E;
        else if (pl <= left && right <= pr)
            return table[i];
        return
            mul(sum(pl, pr, i*2+1, left, (left+right)/2),
                sum(pl, pr, i*2+2, (left+right)/2+1, right));
    }
}


void main() {
    auto N = readln.chomp.to!int;
    auto G = new HLDecomposition(N);
    auto edges = new Tuple!(int, int)[](N-1);
    foreach (i; 0..N-1) {
        auto s = readln.split.map!(to!int);
        G.add_edge(s[0], s[1]);
        G.add_edge(s[1], s[0]);
        edges[i] = tuple(s[0], s[1]);
    }
    
    G.run(0);

    SegmentTree[] st;
    foreach (g; G.groups) {
        st ~= new SegmentTree(g.length.to!int);
    }

    auto Q = readln.chomp.to!int;
    while (Q--) {
        auto q = readln.split;
        if (q[0] == "x") {
            int v = edges[q[1].to!int][1];
            int g = G.nodes[v].group;
            int n = G.nodes[v].number;
            st[g].assign(n, Mat(q[2].to!long, q[3].to!long, q[4].to!long, q[5].to!long));
        } else {
            int u = q[1].to!int;
            int v = q[2].to!int;
            int ug = G.nodes[u].group;
            int un = G.nodes[u].number;
            int vg = G.nodes[v].group;
            int vn = G.nodes[v].number;
            Mat[] ret;
            int g = vg;
            int last = vn;
            while (true) {
                if (g == ug && g == vg) {
                    ret ~= st[g].sum(un+1, vn);
                    break;
                } else if (g == ug) {
                    if (G.groups[g].back != u) {
                        ret ~= st[g].sum(un+1, last);
                    }
                    break;
                } else if (g == vg) {
                    ret ~= st[g].sum(0, vn);
                } else {
                    ret ~= st[g].sum(0, last);
                    g = G.group_parent[g];
                }
                int p = G.group_parent[g];
                g = G.nodes[p].group;
                last = G.nodes[p].number;
            }
            ret.reverse();
            auto ans = Mat(1L, 0L, 0L, 1L);
            foreach (r; ret) ans = mul(ans, r);
            writeln(ans.a, " ", ans.b, " ", ans.c, " ", ans.d);
        }
    }
}
0