結果

問題 No.2337 Equidistant
コンテスト
ユーザー kakel-san
提出日時 2023-06-02 22:17:45
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 2,749 ms / 4,000 ms
コード長 5,031 bytes
コンパイル時間 6,381 ms
コンパイル使用メモリ 117,380 KB
実行使用メモリ 217,612 KB
最終ジャッジ日時 2024-12-28 19:00:25
合計ジャッジ時間 35,622 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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