祖孫詢問#
描述#
已知一顆有根樹。有 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
思路#
將深的那個節點一直往上跳,跳到同一深度後如果是同一個節點那一個就是另一個的祖先。
好吧大概搞懂什麼是倍增了。
第一次把樹寫到結構體裡面。
注意輸入的兩個節點中,後面那個是爸爸。