結果

問題 No.2337 Equidistant
ユーザー 👑 kakel-sankakel-san
提出日時 2023-06-02 22:17:45
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 3,091 ms / 4,000 ms
コード長 5,031 bytes
コンパイル時間 1,938 ms
コンパイル使用メモリ 70,360 KB
実行使用メモリ 225,472 KB
最終ジャッジ日時 2023-08-28 04:02:06
合計ジャッジ時間 34,223 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
21,860 KB
testcase_01 AC 69 ms
21,764 KB
testcase_02 AC 68 ms
19,972 KB
testcase_03 AC 68 ms
19,784 KB
testcase_04 AC 69 ms
21,956 KB
testcase_05 AC 69 ms
21,944 KB
testcase_06 AC 76 ms
23,940 KB
testcase_07 AC 76 ms
23,980 KB
testcase_08 AC 76 ms
21,888 KB
testcase_09 AC 76 ms
21,864 KB
testcase_10 AC 76 ms
21,924 KB
testcase_11 AC 1,383 ms
146,008 KB
testcase_12 AC 1,401 ms
151,992 KB
testcase_13 AC 1,385 ms
147,952 KB
testcase_14 AC 1,381 ms
149,976 KB
testcase_15 AC 1,404 ms
151,988 KB
testcase_16 AC 1,372 ms
150,092 KB
testcase_17 AC 1,426 ms
148,012 KB
testcase_18 AC 1,377 ms
150,032 KB
testcase_19 AC 1,396 ms
147,992 KB
testcase_20 AC 1,376 ms
149,972 KB
testcase_21 AC 2,066 ms
225,472 KB
testcase_22 AC 1,209 ms
143,548 KB
testcase_23 AC 1,258 ms
140,012 KB
testcase_24 AC 2,925 ms
209,300 KB
testcase_25 AC 1,381 ms
152,616 KB
testcase_26 AC 3,091 ms
208,216 KB
testcase_27 AC 1,421 ms
152,544 KB
testcase_28 AC 1,395 ms
154,496 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
    static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, q) = (c[0], c[1]);
        var map = NMap(n - 1);
        var query = NMap(q);
        var tree = new List<int>[n];
        for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>();
        foreach (var edge in map)
        {
            tree[edge[0]].Add(edge[1]);
            tree[edge[1]].Add(edge[0]);
        }
        var ccnt = new Dictionary<int, int>[n];
        for (var i = 0; i < ccnt.Length; ++i) ccnt[i] = new Dictionary<int, int>();
        var csum = new int[n];
        var dlist = new int[n];
        DFS(-1, 0, 0, tree, ccnt, csum, dlist);

        var dmap = DMap(n, 0, tree, dlist);
        var ans = new int[q];
        for (var i = 0; i < q; ++i)
        {
            var s = query[i][0];
            var t = query[i][1];
            var l = LCA(s, t, dmap, dlist);
            if (l.len % 2 == 0)
            {
                if (dlist[s] == dlist[t])
                {
                    
                    var snext = GetAncestor(s, dlist[s] - dlist[l.lca] - 1, dmap);
                    var tnext = GetAncestor(t, dlist[t] - dlist[l.lca] - 1, dmap);
                    ans[i] = n - ccnt[l.lca][snext] - ccnt[l.lca][tnext];
                }
                else if (dlist[s] > dlist[t])
                {
                    var snext = GetAncestor(s, l.len / 2 - 1, dmap);
                    var center = dmap[snext][0];
                    ans[i] = csum[center] - ccnt[center][snext];
                }
                else
                {
                    var tnext = GetAncestor(t, l.len / 2 - 1, dmap);
                    var center = dmap[tnext][0];
                    ans[i] = csum[center] - ccnt[center][tnext];
                }
            }
        }
        WriteLine(string.Join("\n", ans));
    }
    static int DFS(int prev, int cur, int dep, List<int>[] tree, Dictionary<int, int>[] ccnt, int[] csum, int[] dlist)
    {
        dlist[cur] = dep;
        var sum = 1;
        foreach (var next in tree[cur])
        {
            if (prev == next) continue;
            var cnt = DFS(cur, next, dep + 1, tree, ccnt, csum, dlist);
            ccnt[cur][next] = cnt;
            sum += cnt;
        }
        csum[cur] = sum;
        foreach (var next in tree[cur]) if (prev == next)
        {
            ccnt[cur][next] = tree.Length - sum;
        }
        return sum;
    }
    // それぞれの頂点について、2^k個前の親を計算する(ダブリング)
    static List<int>[] DMap(int n, int root, List<int>[] tree, int[] dep)
    {
        var dmap = new List<int>[n];
        for (var i = 0; i < dmap.Length; ++i)
        {
            dmap[i] = new List<int>();
            var p = 0;
            foreach (var parent in tree[i]) if (dep[parent] < dep[i])
            {
                p = parent;
                break;
            }
            dmap[i].Add(p);
        }
        var dpos = 0;
        while (true)
        {
            var comp = true;
            for (var i = 0; i < dmap.Length; ++i)
            {
                var nv = dmap[dmap[i][dpos]][dpos];
                dmap[i].Add(nv);
                if (nv != root) comp = false;
            }
            if (comp) break;
            ++dpos;
        }
        return dmap;
    }
    // ダブリングを使って頂点間の距離を高速に求める
    static (int lca, int len) LCA(int a, int b, List<int>[] dmap, int[] dep)
    {
        if (dep[a] < dep[b]) return LCA(b, a, dmap, dep);
        var res = dep[a] - dep[b];
        while (dep[a] > dep[b])
        {
            var diff = dep[a] - dep[b];
            var bit = 1;
            var pos = 0;
            while (diff > 1)
            {
                bit <<= 1;
                diff >>= 1;
                ++pos;
            }
            a = dmap[a][pos];
        }
        if (a == b) return (dmap[a][0], res);
        while (dmap[a][0] != dmap[b][0])
        {
            for (var i = 1; i < dmap[a].Count; ++i)
            {
                if (dmap[a][i] == dmap[b][i])
                {
                    a = dmap[a][i - 1];
                    b = dmap[b][i - 1];
                    res += 1 << i;
                    break;
                }
            }
        }
        return (dmap[a][0], res + 2);
    }
    static int GetAncestor(int a, int len, List<int>[] dmap)
    {
        while (len > 0)
        {
            var d = 0;
            while (len >= (1 << d + 1)) ++d;
            a = dmap[a][d];
            len -= 1 << d;
        }
        return a;
    }
}
0