#1195720 (C#) No.650 行列木クエリ

• 問題: No.650 行列木クエリ
• ユーザー: 👑 kakel-san
• 提出日時: 2026-10-28 20:43:20
• 言語: C# (.NET 10.0.402 + ACL)
• 結果: AC
• 実行時間: 190 ms / 2,000 ms
• コード長: 5,462 bytes
• コンパイル時間: 9,097 ms
• コンパイル使用メモリ: 170,940 KB
• 実行使用メモリ: 88,208 KB
• 最終ジャッジ日時: 2026-10-28 20:43:35
• 合計ジャッジ時間: 9,907 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 10

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (238 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var map = NArr(n - 1);
        var tree = new List<int>[n];
        for (var i = 0; i < n; ++i) tree[i] = new List<int>();
        foreach (var edge in map)
        {
            tree[edge[0]].Add(edge[1]);
            tree[edge[1]].Add(edge[0]);
        }
        var hld = new HeavyLight(tree, 0);
        var seg = new AtCoder.Segtree<Matrix, SegOp>(n);
        var ans = new List<string>();
        var q = NN;
        for (var i = 0; i < q; ++i)
        {
            var query = ReadLine().Split();
            if (query[0] == "x")
            {
                var idx = int.Parse(query[1]);
                var a = map[idx][0];
                var b = map[idx][1];
                var child = hld.Parent[a] == b ? a : b;
                var mx = new Matrix(int.Parse(query[2]), int.Parse(query[3]), int.Parse(query[4]), int.Parse(query[5]));
                seg[hld.Id[child]] = mx;
            }
            else
            {
                var p = int.Parse(query[1]);
                var c = int.Parse(query[2]);
                var op = new SegOp();
                var cur = op.Identity;
                while (true)
                {
                    if (hld.Head[p] == hld.Head[c])
                    {
                        cur = op.Operate(seg.Prod(hld.Id[p] + 1, hld.Id[c] + 1), cur);
                        break;
                    }
                    if (hld.Head[c] != c)
                    {
                        cur = op.Operate(seg.Prod(hld.Id[hld.Head[c]], hld.Id[c] + 1), cur);
                        c = hld.Parent[hld.Head[c]];
                    }
                    else
                    {
                        cur = op.Operate(seg[hld.Id[c]], cur);
                        c = hld.Parent[hld.Head[c]];
                    }
                }
                ans.Add(cur.ToString());
            }
        }
        WriteLine(string.Join("\n", ans));
    }
    // A B
    // C D
    class Matrix
    {
        public long A;
        public long B;
        public long C;
        public long D;
        public Matrix(long a, long b, long c, long d)
        {
            A = a; B = b; C = c; D = d;
        }
        public override string ToString()
        {
            return $"{A} {B} {C} {D}";
        }
    }
    static int mod = 1_000_000_007;
    struct SegOp : AtCoder.ISegtreeOperator<Matrix>
    {
        public Matrix Identity => new Matrix(1, 0, 0, 1);

        public Matrix Operate(Matrix x, Matrix y)
        {
            return new Matrix((x.A * y.A + x.B * y.C) % mod, (x.A * y.B + x.B * y.D) % mod, (x.C * y.A + x.D * y.C) % mod, (x.C * y.B + x.D * y.D) % mod);
        }
    }
    /// <summary>
    /// 木のHLD(重軽分解)を行う
    /// </summary>
    class HeavyLight
    {
        // 訪問順に頂点の番号を記載 セグメント木などをこの順に格納すればHeavyPathについてのクエリに答えられる
        public int[] Vertex;
        // 頂点ごとに訪問番号を記載 頂点iがHeavyPath上で何番目にあるかは Id[i]-Id[Head[i]] で取得できる
        public int[] Id;
        // HeavyPathのルートとなる頂点番号
        public int[] Head;
        // 部分木のサイズ
        public int[] CCount;
        // 親頂点番号
        public int[] Parent;
        public HeavyLight(List<int>[] tree, int root)
        {
            var n = tree.Length;
            Vertex = new int[n];
            Id = new int[n];
            Head = new int[n];
            CCount = new int[n];
            Parent = new int[n];
            Parent[root] = -1;
            DFS1(-1, root, tree);
            var count = 0;
            DFS2(-1, root, tree, root, ref count);
        }
        void DFS1(int prev, int cur, List<int>[] tree)
        {
            ++CCount[cur];
            foreach (var next in tree[cur])
            {
                if (prev == next) continue;
                Parent[next] = cur;
                DFS1(cur, next, tree);
                CCount[cur] += CCount[next];
            }
        }
        void DFS2(int prev, int cur, List<int>[] tree, int head, ref int count)
        {
            Vertex[count] = cur;
            Id[cur] = count;
            ++count;
            Head[cur] = head;
            var maxcc = 0;
            var maxcid = -1;
            foreach (var next in tree[cur])
            {
                if (prev == next) continue;
                if (maxcc < CCount[next])
                {
                    maxcc = CCount[next];
                    maxcid = next;
                }
            }
            if (maxcid >= 0) DFS2(cur, maxcid, tree, head, ref count);
            foreach (var next in tree[cur])
            {
                if (prev == next || maxcid == next) continue;
                DFS2(cur, next, tree, next, ref count);
            }
        }
    }
}