2297 問題 D: 藍(lán)橋杯2018年第九屆真題-版本分支
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 892 解決: 108
題目描述
小明負(fù)責(zé)維護(hù)公司一個(gè)奇怪的項(xiàng)目。這個(gè)項(xiàng)目的代碼一直在不斷分支(branch)但是從未發(fā)生過合并(merge)。
現(xiàn)在這個(gè)項(xiàng)目的代碼一共有N個(gè)版本，編號(hào)1~N，其中1號(hào)版本是最初的版本。
除了1號(hào)版本之外，其他版本的代碼都恰好有一個(gè)直接的父版本；即這N個(gè)版本形成了一棵以1為根的樹形結(jié)構(gòu)。
如下圖就是一個(gè)可能的版本樹：
1
/ \
2 3
| / \
5 4 6
現(xiàn)在小明需要經(jīng)常檢查版本x是不是版本y的祖先版本。你能幫助小明嗎？
輸入
第一行包含兩個(gè)整數(shù)N和Q，代表版本總數(shù)和查詢總數(shù)。
以下N-1行，每行包含2個(gè)整數(shù)u和v，代表版本u是版本v的直接父版本。
再之后Q行，每行包含2個(gè)整數(shù)x和y，代表詢問版本x是不是版本y的祖先版本。
輸出
對(duì)于每個(gè)詢問，輸出YES或NO代表x是否是y的祖先。
樣例輸入
6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情