#1147246 (C#) No.901 K-ary εxtrεεmε

• 問題: No.901 K-ary εxtrεεmε
• ユーザー: kakel-san
• 提出日時: 2026-02-08 00:02:45
• 言語: C# (.NET 10.0.102)
• 結果: WA
• 実行時間: -
• コード長: 17,646 bytes
• コンパイル時間: 19,586 ms
• コンパイル使用メモリ: 170,616 KB
• 実行使用メモリ: 266,992 KB
• 最終ジャッジ日時: 2026-02-08 00:03:35
• 合計ジャッジ時間: 49,619 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 1
other	AC * 8 WA * 21

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (126 ミリ秒)。
  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 q = NN;
        var query = NArr(q);
        var tree = new List<(int to, long len)>[n];
        for (var i = 0; i < n; ++i) tree[i] = new List<(int to, long len)>();
        foreach (var edge in map)
        {
            tree[edge[0]].Add((edge[1], edge[2]));
            tree[edge[1]].Add((edge[0], edge[2]));
        }
        var order = new List<int>(n);
        DFS(0, -1, tree, order);
        var posorder = new int[n];
        for (var i = 0; i < n; ++i) posorder[order[i]] = i;
        
        var lca = new LCA(tree);
        var ans = new long[q];
        for (var i = 0; i < q; ++i)
        {
            var list = new List<(int id, int ord)>(query[i].Length);
            for (var j = 1; j < query[i].Length; ++j) list.Add((query[i][j], posorder[query[i][j]]));
            list.Sort((l, r) => l.ord.CompareTo(r.ord));
            var infolist = new List<Info>();
            var t = new AvlTree<Info>();
            var pq = new PriorityQueue<Info, int>();
            for (var j = 1; j < list.Count; ++j)
            {
                var dist = lca.Distance(list[j - 1].id, list[j].id);
                var info = new Info(j - 1, list[j - 1].id, list[j].id, dist.lca, posorder[list[j - 1].id], dist.w);
                infolist.Add(info);
                t.Insert(info);
                pq.Enqueue(info, -lca.GetDepth(info.Lca));
            }
            // WriteLine(string.Join(" ", infolist));
            while (pq.Count > 0)
            {
                var info = pq.Dequeue();
                if (info.Deleted) continue;
                ans[i] += info.Len;
                var ipos = 0;
                t.LowerBound(info, ref ipos);
                Info ins1 = null;
                if (ipos > 0)
                {
                    var left = t.ElementAt(ipos - 1);
                    t.Delete(left);
                    left.Deleted = true;
                    var dist = lca.Distance(left.Left, info.Lca);
                    ins1 = new Info(infolist.Count, left.Left, info.Lca, dist.lca, posorder[left.Left], dist.w);
                }
                Info ins2 = null;
                if (ipos + 1 < t.GetCount())
                {
                    var right = t.ElementAt(ipos + 1);
                    t.Delete(right);
                    right.Deleted = true;
                    var dist = lca.Distance(info.Lca, right.Right);
                    ins2 = new Info(infolist.Count + (ins1 == null ? 0 : 1), info.Lca, right.Right, dist.lca, posorder[info.Lca], dist.w);
                }
                t.Delete(info);
                // WriteLine($"out : {info}");
                if (ins1 != null)
                {
                    infolist.Add(ins1);
                    t.Insert(ins1);
                    pq.Enqueue(ins1, -lca.GetDepth(ins1.Lca));
                    // WriteLine($"in : {ins1}");
                }
                if (ins2 != null)
                {
                    infolist.Add(ins2);
                    t.Insert(ins2);
                    pq.Enqueue(ins2, -lca.GetDepth(ins2.Lca));
                    // WriteLine($"in : {ins2}");
                }
            }
        }
        WriteLine(string.Join("\n", ans));
    }
    class Info : IComparable<Info>
    {
        public int Id;
        public int Left;
        public int Right;
        public int Lca;
        public int LeftOrd;
        public long Len;
        public bool Deleted;
        public Info(int id, int left, int right, int lca, int leftord, long len)
        {
            Id = id; Left = left; Right = right; Lca = lca; LeftOrd = leftord; Len = len;
        }
        public int CompareTo(Info b)
        {
            return LeftOrd.CompareTo(b.LeftOrd);
        }
        public override string ToString()
        {
            return $"({Id}, {Left}, {Right}, {Lca}, {LeftOrd}, {Len}, {Deleted})";
        }
    }
    static void DFS(int cur, int prev, List<(int to, long len)>[] tree, List<int> order)
    {
        order.Add(cur);
        foreach (var next in tree[cur])
        {
            if (next.to == prev) continue;
            DFS(next.to, cur, tree, order);
        }
    }
    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);
        }
        public int GetDepth(int cur)
        {
            return depth[cur];
        }
        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;
        }
    }
    public class AvlTree<T> where T: IComparable<T>
    {
        private class Node<U> where U: IComparable<U>
        {
            public U Value;
            public Node<U> Lc = null;
            public Node<U> Rc = null;
            public int Height;
            public int Count;
            public int CCount;
            public Node(int height, U value)
            {
                Height = height;
                Count = 1;
                CCount = 1;
                Value = value;
            }
        }
        private Node<T> root = null;
        static int GetHeight(Node<T> t)
        {
            return t == null ? 0 : t.Height;
        }
        static int GetCount(Node<T> t)
        {
            return t == null ? 0 : t.Count;
        }
        static int GetBalance(Node<T> t)
        {
            return GetHeight(t.Lc) - GetHeight(t.Rc);
        }
        static void Recalc(Node<T> t)
        {
            if (t == null) return;
            t.Height = 1 + Math.Max(GetHeight(t.Lc), GetHeight(t.Rc));
            t.Count = t.CCount + GetCount(t.Lc) + GetCount(t.Rc);
        }
        static Node<T> RotateLeft(Node<T> t)
        {
            Node<T> u = t.Rc;
            Node<T> t2 = u.Lc;
            u.Lc = t;
            t.Rc = t2;
            Recalc(t);
            Recalc(u);
            return u;
        }
        static Node<T> RotateRight(Node<T> t)
        {
            Node<T> u = t.Lc;
            Node<T> t2 = u.Rc;
            u.Rc = t;
            t.Lc = t2;
            Recalc(t);
            Recalc(u);
            return u;
        }
        static Node<T> RotateLR(Node<T> t)
        {
            t.Lc = RotateLeft(t.Lc);
            return RotateRight(t);
        }
        static Node<T> RotateRL(Node<T> t)
        {
            t.Rc = RotateRight(t.Rc);
            return RotateLeft(t);
        }
        static Node<T> BalanceLeft(Node<T> t)
        {
            if (GetBalance(t) > 1)
            {
                if (GetBalance(t.Lc) < 0) t = RotateLR(t);
                else t = RotateRight(t);
            }
            Recalc(t);
            return t;
        }
        static Node<T> BalanceRight(Node<T> t)
        {
            if (GetBalance(t) < -1)
            {
                if (GetBalance(t.Rc) > 0) t = RotateRL(t);
                else t = RotateLeft(t);
            }
            Recalc(t);
            return t;
        }
        /// <summary>valueを挿入する</summary>
        public void Insert(T value)
        {
            root = Insert(root, value);
        }
        Node<T> Insert(Node<T> cur, T value)
        {
            if (cur == null)
            {
                return new Node<T>(1, value);
            }
            var d = value.CompareTo(cur.Value);
            if (d < 0)
            {
                cur.Lc = Insert(cur.Lc, value);
                return BalanceLeft(cur);
            }
            else if (d > 0)
            {
                cur.Rc = Insert(cur.Rc, value);
                return BalanceRight(cur);
            }
            else
            {
                ++cur.CCount;
                Recalc(cur);
                return cur;
            }
        }
        /// <summary>valueを削除する 存在しない場合はなにもしない</summary>
        public void Delete(T value)
        {
            root = Delete(root, value);
        }
        Node<T> Delete(Node<T> cur, T value)
        {
            if (cur == null) return null;
            var d = value.CompareTo(cur.Value);
            if (d < 0)
            {
                cur.Lc = Delete(cur.Lc, value);
                return BalanceRight(cur);
            }
            else if (d > 0)
            {
                cur.Rc = Delete(cur.Rc, value);
                return BalanceLeft(cur);
            }
            else
            {
                --cur.CCount;
                if (cur.CCount == 0)
                {
                    if (cur.Lc != null)
                    {
                        Node<T> del = null;
                        var max = DeleteMax(cur.Lc, ref del);
                        cur.Lc = max;
                        cur.Value = del.Value;
                        cur.CCount = del.CCount;
                        return BalanceRight(cur);
                    }
                    else
                    {
                        return cur.Rc;
                    }
                }
                else
                {
                    Recalc(cur);
                    return cur;
                }
            }
        }
        Node<T> DeleteMax(Node<T> t, ref Node<T> del)
        {
            if (t.Rc == null)
            {
                del = t;
                return t.Lc;
            }
            else
            {
                var max = DeleteMax(t.Rc, ref del);
                t.Rc = max;
                return BalanceLeft(t);
            }
        }
        /// <summary>小さいほうからpos番目の要素を取得する</summary>
        public T ElementAt(int pos)
        {
            if (pos < 0 || pos >= GetCount(root)) return default;
            var t = ElementAt(root, pos);
            return t.Value;
        }
        /// <summary>小さいほうからpos番目の要素を取得する</summary>
        public T ElementAt(int pos, T defaultValue)
        {
            if (pos < 0 || pos >= GetCount(root)) return defaultValue;
            return ElementAt(pos);
        }
        Node<T> ElementAt(Node<T> cur, int pos)
        {
            if (pos < GetCount(cur.Lc)) return ElementAt(cur.Lc, pos);
            if (pos < GetCount(cur.Lc) + cur.CCount) return cur;
            if (pos < cur.Count) return ElementAt(cur.Rc, pos - GetCount(cur.Lc) - cur.CCount);
            return null;
        }
        public void Debug()
        {
            if (root == null) return;
            Console.WriteLine($"root val:{root.Value}, CCount:{root.CCount}, Count:{root.Count}");
            Debug(root.Value, root.Lc);
            Debug(root.Value, root.Rc);
        }
        void Debug(T pval, Node<T> cur)
        {
            if (cur == null) return;
            Console.WriteLine($"{pval} -> val:{cur.Value}, CCount:{cur.CCount}, Count:{cur.Count}");
            Debug(cur.Value, cur.Lc);
            Debug(cur.Value, cur.Rc);
        }
        /// <summary>value以上でもっとも小さい値とその場所を返却する そのようなものが存在しなければデフォルト値を返す</summary>
        public T LowerBound(T value, ref int index)
        {
            var cur = root;
            T ans = default;
            var add = 0;
            index = GetCount(root);
            while (cur != null)
            {
                if (value.CompareTo(cur.Value) <= 0)
                {
                    ans = cur.Value;
                    index = add + GetCount(cur.Lc);
                    cur = cur.Lc;
                }
                else
                {
                    add += GetCount(cur.Lc) + cur.CCount;
                    cur = cur.Rc;
                }
            }
            return ans;
        }
        /// <summary>要素の個数を求める</summary>
        public int GetCount()
        {
            return GetCount(root);
        }
        /// <summary>要素の一覧を返す</summary>
        public List<T> GetValues()
        {
            var list = new List<T>();
            if (root != null) GetValues(root, list);
            return list;
        }
        static void GetValues(Node<T> cur, List<T> list)
        {
            if (cur.Lc != null) GetValues(cur.Lc, list);
            list.Add(cur.Value);
            if (cur.Rc != null) GetValues(cur.Rc, list);
        }
        /// <summary>指定された要素が存在するか求める</summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool Contains(T value)
        {
            if (root == null) return false;
            return Contains(root, value);
        }
        static bool Contains(Node<T> cur, T value)
        {
            var d = cur.Value.CompareTo(value);
            if (d == 0) return true;
            if (d > 0)
            {
                if (cur.Lc == null) return false;
                return Contains(cur.Lc, value);
            }
            else
            {
                if (cur.Rc == null) return false;
                return Contains(cur.Rc, value);
            }
        }
    }
}