結果

問題 No.2337 Equidistant
コンテスト
ユーザー FromBooska
提出日時 2023-06-02 22:03:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,569 bytes
コンパイル時間 901 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 176,368 KB
最終ジャッジ日時 2024-12-28 18:07:17
合計ジャッジ時間 34,298 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 25
権限があれば一括ダウンロードができます

ソースコード

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