題目描述
小倉鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每個節點的編號為1~n，地下洞穴是一個樹形結構，這一天小倉鼠打算從從他的臥室（a）到餐廳（b），而他的基友同時要從他的臥室（c）到圖書館（d），他們都會走最短路徑，現在小倉鼠希望知道，有沒有可能在某個地方，可以碰到他的基友？
小倉鼠那么弱，還要天天被zzq大爺虐，請你快來救救他吧！
輸入格式
第一行兩個正整數n和q，表示這棵樹節點的個數和詢問的個數，
接下來n-1行，每行兩個正整數u和v，表示節點u到節點v之間有一條邊，
接下來q行，每行四個正整數a、b、c和d，表示節點編號，也就是一次詢問，其意義如上，
輸出格式
對于每個詢問，如果有公共點，輸出大寫字母“Y”；否則輸出“N”，
輸入輸出樣例
輸入
5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4
輸出
Y
N
Y
Y
Y
資料范圍
20%的資料 n<=200,q<=200
40%的資料 n<=2000,q<=2000
70%的資料 n<=50000,q<=50000
100%的資料 n<=100000,q<=100000
思路一
- 根據題意，我們要做的就是判斷這兩條路徑是否相交，所以我們可以把兩條路徑經過的點都標記一下，如果有某個點被標記了兩次，那么這個點就是一個公共點，如果沒有標記了兩次的點，那么就說明沒有公共點，
- 標記路徑上的點可以用樹上差分，
- 復雜度O（n*q），
思路二
- 通過模擬我們可以發現，如果這兩條路徑相交，那么一定有一條路徑的lca在另一條路徑上，所以我們只需判斷兩次即可，
- 如果一個點在路徑上，那么這個點到兩端點的距離和等于兩端點間的距離，
- 距離通過lca來求，
- 復雜度O(n*logn），
思路三
- 前面與思路一相同，
- 用樹剖給路徑打標記，同時維護區間最大標記值，判斷是否為2，
- 復雜度O(n*logn)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231064.html
標籤：其他