結果

問題 No.898 tri-βutree
コンテスト
ユーザー kakel-san
提出日時 2026-01-22 23:15:18
言語 C#
(.NET 10.0.101)
結果
AC  
実行時間 746 ms / 4,000 ms
コード長 5,587 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,601 ms
コンパイル使用メモリ 171,172 KB
実行使用メモリ 251,444 KB
最終ジャッジ日時 2026-01-22 23:15:50
合計ジャッジ時間 25,572 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (120 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
using System.Security.Cryptography;
using Microsoft.VisualBasic;

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 q = NN;
        var query = NArr(q);
        var tree = new List<(int to, long w)>[n];
        for (var i = 0; i < n; ++i) tree[i] = new List<(int to, long w)>();
        foreach (var edge in map)
        {
            tree[edge[0]].Add((edge[1], edge[2]));
            tree[edge[1]].Add((edge[0], edge[2]));
        }
        var lca = new LCA(tree);
        var ans = new long[q];
        for (var i = 0; i < q; ++i)
        {
            var x = query[i][0];
            var y = query[i][1];
            var z = query[i][2];
            var xy = lca.Distance(x, y);
            var yz = lca.Distance(y, z);
            var zx = lca.Distance(z, x);
            ans[i] = Math.Min(xy.w + lca.Distance(xy.lca, z).w, Math.Min(yz.w + lca.Distance(yz.lca, x).w, zx.w + lca.Distance(zx.lca, y).w));
        }
        WriteLine(string.Join("\n", ans));
    }
    // 木の最小共通祖先(LCA)を求める
    // 頂点間の距離を高速に求める
    class LCA
    {
        int[] depth;
        long[] wdepth;
        List<int>[] dmap;
        /// <summary>辺の距離がすべて1のときのLCAを求められる初期設定</summary>
        /// <param name="tree">木</param>
        public LCA(List<int>[] tree)
        {
            depth = new int[tree.Length];
            var maxDepth = DepthList(-1, 0, 0, tree);
            wdepth = new long[tree.Length];
            for (var i = 0; i < tree.Length; ++i) wdepth[i] = depth[i];

            dmap = new List<int>[tree.Length];
            for (var i = 0; i < dmap.Length; ++i) dmap[i] = new List<int>();
            for (var i = 0; i < dmap.Length; ++i)
            {
                var nx = -1;
                foreach (var next in tree[i]) if (depth[next] < depth[i]) nx = next;
                dmap[i].Add(nx);
            }
            for (int d = 2, j = 0; d <= maxDepth; d *= 2, ++j) for (var i = 0; i < dmap.Length; ++i)
            {
                var nx = -1;
                if (dmap[i][j] > -1) nx = dmap[dmap[i][j]][j];
                dmap[i].Add(nx);
            }
        }
        /// <summary>辺の距離が設定されているときのLCAを求められる初期設定</summary>
        /// <param name="tree">木</param>
        public LCA(List<(int to, long w)>[] tree)
        {
            depth = new int[tree.Length];
            wdepth = new long[tree.Length];
            var maxDepth = DepthList(-1, 0, 0, tree);

            dmap = new List<int>[tree.Length];
            for (var i = 0; i < dmap.Length; ++i) dmap[i] = new List<int>();
            for (var i = 0; i < dmap.Length; ++i)
            {
                var nx = -1;
                foreach (var next in tree[i]) if (depth[next.to] < depth[i]) nx = next.to;
                dmap[i].Add(nx);
            }
            for (int d = 2, j = 0; d <= maxDepth; d *= 2, ++j) for (var i = 0; i < dmap.Length; ++i)
            {
                var nx = -1;
                if (dmap[i][j] > -1) nx = dmap[dmap[i][j]][j];
                dmap[i].Add(nx);
            }
        }
        public (int d, long w, int lca) Distance(int x, int y)
        {
            var res = 0;
            if (depth[x] < depth[y]) (x, y) = (y, x);
            var xw = wdepth[x];
            var yw = wdepth[y];
            while (depth[x] > depth[y])
            {
                for (var b = dmap[x].Count - 1; b >= 0; --b)
                {
                    var move = 1 << b;
                    if (depth[x] - depth[y] >= move)
                    {
                        x = dmap[x][b];
                        res += move;
                    }
                }
            }
            for (var b = dmap[x].Count - 1; b >= 0; --b)
            {
                if (dmap[x][b] != dmap[y][b])
                {
                    x = dmap[x][b];
                    y = dmap[y][b];
                    res += 2 << b;
                }
            }
            var lca = x;
            if (x != y)
            {
                res += 2;
                lca = dmap[x][0];
            }
            return (res, xw + yw - 2 * wdepth[lca], lca);
        }
        int DepthList(int prev, int cur, int d, List<int>[] tree)
        {
            depth[cur] = d;
            var max = d;
            foreach (var next in tree[cur])
            {
                if (next == prev) continue;
                max = Math.Max(max, DepthList(cur, next, d + 1, tree));
            }
            return max;
        }
        int DepthList(int prev, int cur, int d, List<(int to, long w)>[] tree)
        {
            depth[cur] = d;
            var max = d;
            foreach (var next in tree[cur])
            {
                if (next.to == prev) continue;
                wdepth[next.to] = wdepth[cur] + next.w;
                max = Math.Max(max, DepthList(cur, next.to, d + 1, tree));
            }
            return max;
        }
    }
}
0