結果

問題 No.2337 Equidistant
ユーザー navel_tosnavel_tos
提出日時 2023-06-03 02:00:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,950 ms / 4,000 ms
コード長 3,719 bytes
コンパイル時間 489 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 342,360 KB
最終ジャッジ日時 2024-06-09 03:08:17
合計ジャッジ時間 28,785 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
53,576 KB
testcase_01 AC 32 ms
54,048 KB
testcase_02 AC 33 ms
54,196 KB
testcase_03 AC 35 ms
53,536 KB
testcase_04 AC 32 ms
54,496 KB
testcase_05 AC 30 ms
53,420 KB
testcase_06 AC 112 ms
79,460 KB
testcase_07 AC 128 ms
79,588 KB
testcase_08 AC 119 ms
79,060 KB
testcase_09 AC 114 ms
79,064 KB
testcase_10 AC 113 ms
79,124 KB
testcase_11 AC 1,408 ms
169,932 KB
testcase_12 AC 1,179 ms
170,076 KB
testcase_13 AC 1,192 ms
169,316 KB
testcase_14 AC 1,429 ms
169,180 KB
testcase_15 AC 1,443 ms
169,680 KB
testcase_16 AC 1,195 ms
169,440 KB
testcase_17 AC 1,441 ms
170,332 KB
testcase_18 AC 1,152 ms
169,440 KB
testcase_19 AC 1,241 ms
170,220 KB
testcase_20 AC 1,442 ms
169,668 KB
testcase_21 AC 1,559 ms
340,800 KB
testcase_22 AC 1,035 ms
195,296 KB
testcase_23 AC 1,423 ms
176,216 KB
testcase_24 AC 1,797 ms
340,980 KB
testcase_25 AC 1,516 ms
176,568 KB
testcase_26 AC 1,950 ms
342,360 KB
testcase_27 AC 1,490 ms
175,956 KB
testcase_28 AC 1,514 ms
175,812 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder391D Equidistant

'''
解説ACを目指す。

LCA使うところまでは良いが、部分木の頂点数を用いて計算できる点に着目できなかったのが敗因。
くやしいな。
'''
#最小共通祖先 ライブラリ
class LowestCommonAncestor:
    def __init__(self,n):
        self._n=n;n=0
        while 2**(n/10)<self._n:n+=1
        self._logn=int(n/10+2);self._depth=[0 for _ in [0]*self._n];self._distance=[0 for _ in [0]*self._n];self._ancestor=[[-1 for _ in [0]*self._n] for k in [0]*self._logn];self._edge=[[] for _ in [0]*self._n]
    def add_edge(self,u,v,w=1):self._edge[u].append((v,w));self._edge[v].append((u,w))
    def build(self,root=0):  #rootを指定し、その他の頂点に祖先情報を書き込む
        stack=[root]
        while stack:
            now=stack.pop()
            for nxt,w in self._edge[now]:
                if self._ancestor[0][nxt]!=now and self._ancestor[0][now]!=nxt:self._ancestor[0][nxt]=now;self._depth[nxt]=self._depth[now]+1;self._distance[nxt]=self._distance[now]+w;stack.append(nxt)
        for k in range(1,self._logn):
            for i in range(self._n):
                if self._ancestor[k-1][i]==-1:self._ancestor[k][i]=-1
                else:self._ancestor[k][i]=self._ancestor[k-1][self._ancestor[k-1][i]]
    def LCA(self,u,v):
        if self._depth[u]>self._depth[v]:u,v=v,u
        for k in range(self._logn-1,-1,-1):v=self._ancestor[k][v] if((self._depth[v]-self._depth[u])>>k)&1 else v
        if u==v:return u
        for k in range(self._logn-1,-1,-1):  #ギリギリ一致する直前まで祖先を辿る
            if self._ancestor[k][u]!=self._ancestor[k][v]:
                u,v=self._ancestor[k][u],self._ancestor[k][v]
        return self._ancestor[0][u]
    def distance(self,u,v):return self._distance[u]+self._distance[v]-2*self._distance[self.LCA(u,v)]


import sys; sys.setrecursionlimit(10**7); input=sys.stdin.readline
f=lambda:list(map(int,input().split()))

#入力受取
N,Q=f(); G=[[] for _ in range(N)]; LCA=LowestCommonAncestor(N)
for _ in range(N-1): a,b=f(); G[a-1].append(b-1); G[b-1].append(a-1); LCA.add_edge(a-1,b-1)

#なにかと面倒なので、親は次数1の頂点に固定
for P in range(N):
    if len(G[P])==1: break

#Vert[i]: 頂点iを親とする部分木の頂点数
Vert=[0]*N; LCA.build(P)

#DFS: 部分木の頂点数を計算
def yukicoder391D(now,back,vertice):
    vertice+=1; save=vertice; Vert[now]+=1
    for next in G[now]:
        if next==back: continue
        vertice=yukicoder391D(next,now,vertice)
        Vert[now]+=vertice-save; save=vertice
    return vertice
yukicoder391D(P,-1,0)

#タスクに回答
for _ in range(Q):
    a,b=f(); a-=1; b-=1; x=LCA.LCA(a,b)
    dx=LCA._distance[x]; da,db=LCA._distance[a]-dx,LCA._distance[b]-dx
    if (da+db)%2: print(0); continue
    if da==db:  #答えは頂点xから親方向のものすべて
        #xに入る直前まで頂点a,bを下げ、その部分木の頂点数ぶん減らした値が答え
        da-=1; bita=bin(da)[2:]; La=len(bita)
        for i in range(La):
            pos=La-1-i
            if bita[i]=='1': a=LCA._ancestor[pos][a]; b=LCA._ancestor[pos][b]
        print(N-Vert[a]-Vert[b])
    else:
        a,b,da,db=(a,b,da,db) if da<db else (b,a,db,da)  #dbが常に大きい
        #a: 中点xより親側はNG  b: 中点xより子側はNG とすればよい
        #このうち、aは部分木にはじめからカウントされていないので、bだけ下げる
        mid=(da+db)//2-1; bitm=bin(mid)[2:]; Lm=len(bitm)
        for i in range(Lm):
            pos=Lm-1-i
            if bitm[i]=='1': b=LCA._ancestor[pos][b]
        print(Vert[LCA._ancestor[0][b]]-Vert[b])
0