BuringStraw

BuringStraw

CQYZ OJ|競賽 133|祖孫詢問

祖孫詢問#

描述#

已知一顆有根樹。有 m 個詢問。每個詢問給出了一對節點 x,y, 輸出 x,y 的祖孫關係

輸入#

第一行節點數目 n 接下來 n 行,每行一對整數 a,b, 表示 a 和 b 之間有邊。如果 b==-1,那麼 a 就是數根接下來是一個整數 m,表示詢問的個數接下來 m 行,每行兩個正整數 x,y

輸出#

對於每一個詢問,如果 x 是 y 的祖先,輸出 1;如果 y 是 x 的祖先,輸出 2;否則輸出 0

輸入範例 1#

輸出範例 1#

提示#

對於 30% 的數據,n,m<=1000 對於 100% 的數據,n,m<=40000, 每個節點的編號都不超過 40000

思路#

將深的那個節點一直往上跳,跳到同一深度後如果是同一個節點那一個就是另一個的祖先。

好吧大概搞懂什麼是倍增了。

第一次把樹寫到結構體裡面。

注意輸入的兩個節點中,後面那個是爸爸。

Code#

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。