結果

問題 No.650 行列木クエリ
ユーザー nebukuro09nebukuro09
提出日時 2018-02-10 02:50:08
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 3,761 bytes
コンパイル時間 980 ms
コンパイル使用メモリ 131,196 KB
実行使用メモリ 26,764 KB
最終ジャッジ日時 2024-06-12 23:51:26
合計ジャッジ時間 5,239 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,884 KB
testcase_01 AC 65 ms
13,248 KB
testcase_02 AC 190 ms
25,344 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 65 ms
12,584 KB
testcase_05 AC 196 ms
26,764 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 TLE -
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;

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


void main() {
    auto N = readln.chomp.to!int;
    auto G = new int[][](N);
    auto M = new Mat[](N);
    auto E = new Tuple!(int, int)[](N-1);
    foreach (i; 0..N-1) {
        auto s = readln.split.map!(to!int);
        G[s[0]] ~= s[1];
        G[s[1]] ~= s[0];
        E[i] = tuple(s[0], s[1]);
    }
    auto P = new int[](N);
    auto C = new int[](N);
    int[][] HL;
    int[] HL_rev = new int[](N);
    int[][] HLG;
    int[] HLP;
    Mat[] HLM;
    M.fill(Mat(1, 0, 0, 1));

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

    void dfs2(int n, int g, int p, bool heavy) {
        if (heavy) {
            HL[g] ~= n;
        } else {
            g = HL.length.to!int;
            HL ~= [n];
        }
        HL_rev[n] = g;

        int mx = -1;
        foreach (m; G[n]) if (m != p) mx = max(mx, C[m]);
        bool h = false;

        foreach (m; G[n]) {
            if (m == p) continue;
            if (!h && C[m] == mx) {
                h = true;
                dfs2(m, g, n, true);
            } else {
                dfs2(m, g, n, false);
            }
        }
    }

    void update(int n, Mat mat) {
        n = E[n][1];
        M[n] = mat;
        int g = HL_rev[n];
        HLM[HL[g][0]] = M[HL[g][0]];
        foreach (i; 0..HL[g].length.to!int-1) {
            HLM[HL[g][i+1]] = mul(HLM[HL[g][i]], M[HL[g][i+1]]);
        }
    }

    Mat query(int u, int v) {
        auto tmp = Mat(1, 0, 0, 1);
        int ug = HL_rev[u];
        int vg = HL_rev[v];

        if (ug == vg) {
            bool ok = false;
            foreach (n; HL[ug]) {
                if (ok) {
                    tmp = mul(tmp, M[n]);
                }
                if (n == u) ok = true;
                if (n == v) return tmp;
            }
        }


        foreach (n; HL[vg]) {
            tmp = mul(tmp, M[n]);
            if (n == v) break;
        }

        Mat[] ret = [tmp];
        int cur = P[HL[vg][0]];

        while (HL_rev[cur] != ug) {
            ret ~= HLM[cur];
            cur = P[HL[HL_rev[cur]][0]];
        }

        tmp = Mat(1, 0, 0, 1);
        bool ok = false;
        foreach (n; HL[ug]) {
            if (ok) {
                tmp = mul(tmp, M[n]);
            }
            if (n == u) ok = true;
            if (n == cur) break;
        }
        ret ~= tmp;

        ret.reverse();
        Mat ans = Mat(1, 0, 0, 1);
        foreach (mat; ret) {
            ans = mul(ans, mat);
        }

        return ans;
    }

    dfs1(0, -1);
    dfs2(0, 0, -1, false);

    foreach (i; 0..N-1) {
        if (P[E[i][0]] == E[i][1]) swap(E[i][0], E[i][1]);
    }

    int group = HL.length.to!int;
    HLM = N.iota.map!(i => Mat(1, 0, 0, 1)).array;
    HLG = new int[][](group);
    HLP = new int[](group);
    HLP[0] = -1;


    auto Q = readln.chomp.to!int;

    while (Q--) {
        auto q = readln.split;
        if (q[0] == "x") {
            update(q[1].to!int, Mat(q[2].to!long, q[3].to!long, q[4].to!long, q[5].to!long));
        } else {
            auto ans = query(q[1].to!int, q[2].to!int);
            writeln(ans.a, " ", ans.b, " ", ans.c, " ", ans.d);
        }
    }
}

Mat mul(Mat X, Mat Y) {
    Mat 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);
    ret.a %= MOD;
    ret.b %= MOD;
    ret.c %= MOD;
    ret.d %= MOD;
    return ret;
}
0