結果

問題 No.2337 Equidistant
ユーザー FromBooskaFromBooska
提出日時 2023-06-02 22:03:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,569 bytes
コンパイル時間 657 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 176,500 KB
最終ジャッジ日時 2024-06-08 23:12:35
合計ジャッジ時間 33,613 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,736 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 1,393 ms
154,084 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 1,610 ms
152,916 KB
testcase_25 WA -
testcase_26 AC 1,489 ms
150,036 KB
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# オイラーツアーかなー
# st間の距離は求まる
# それが奇数なら0
# しかし偶数のときはそこから出る枝の数が必要
# 毎クエリで距離同じ頂点をカウントしたら間に合わないよな

# 木の頂点間の距離を高速に求める
# LCAパッケージ
# 使い方はこの例を見るしかない
# dummy, depth = LCA.query(a, b)で共通祖先からのdepth
# LCA.tour[LCA.in_time[a]][1]でルート1からのaまでの距離

# 違うLCAでやったらTLEしたのでこちらの人のを借用
# https://atcoder.jp/contests/abc014/submissions/37274146

# LCA
class LCA():
    def __init__(self, N, graph, root):
        self.tour, self.in_time = self.EulerTour(N, graph, root)
        self.seg = self.SegTree(self.tour)

    def query(self, u, v):
        uu = self.in_time[u]
        vv = self.in_time[v]
        if vv < uu:
            uu, vv = vv, uu
        position, depth = self.seg.query(uu, vv+1)
        return position, depth

    def EulerTour(self, N, graph, root):
        used = [False]*N
        q = [~root, root]
        tour = []
        in_time = [-1]*N
        time = -1
        d = -1
        while q:
            u = q.pop()
            if u < 0:
                time += 1
                if -N <= u:
                    d -= 1
                tour.append((u, d))
            if u >= 0:
                time += 1
                if in_time[u] < 0:
                    in_time[u] = time
                d += 1
                tour.append((u, d))
                flg = False
                for v in graph[u]:
                    if used[v]:
                        continue
                    used[v] = True
                    if flg:
                        q.append(~u-N)
                    q.append(~v)
                    q.append(v)
                    flg = True
        return tour, in_time

    class SegTree:
        def segfunc(self, x, y):
            if x[1] < y[1]:
                return x
            return y

        def __init__(self, init_val):
            n = len(init_val)
            self.ide_ele = (10**10, 10**10)
            self.num = 1 << (n-1).bit_length()
            self.tree = [self.ide_ele]*2*self.num
            for i in range(n):
                self.tree[self.num+i] = init_val[i]
            for i in range(self.num-1, 0, -1):
                self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])

        def query(self, l, r):
            res = self.ide_ele
            l += self.num
            r += self.num
            while l < r:
                if l & 1:
                    res = self.segfunc(res, self.tree[l])
                    l += 1
                if r & 1:
                    res = self.segfunc(res, self.tree[r-1])
                l >>= 1
                r >>= 1
            return res
          
N, Q = map(int, input().split())
edges = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

LCA = LCA(N+1, edges, 1) #3番目はルート
for q in range(Q):
    s, t = map(int, input().split())
    dummy, depth = LCA.query(s, t)
    # 第2varがLCA共通祖先からのdepth
    distance_s = LCA.tour[LCA.in_time[s]][1]
    # これでaから1の距離、つまりルートからの距離
    distance_t = LCA.tour[LCA.in_time[t]][1]
    distance_st = distance_s + distance_t - depth*2
    if distance_st%2 == 1:
        print(0)
    else:
        print(1)
        # いや、違うよな、その頂点からst方向以外に出ている葉の数
0