TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

23.3% (7/30)

Description

瓦干達(Wakanda)是一個南非洲的國家,這個國家有 $N$ 座城市編號 $1 \sim N$,還有 $N-1$ 條雙向的馬路連接其中兩個城市,且每座城市都恰有一條路徑(經由若干條馬路)達到另一個城市。

一場馬拉松即將舉辦於瓦干達,馬拉松選手將會從一座城市跑到另一座城市。沿途可能會經過好幾座城市,而每個城市都設有休息站。

因為馬拉松選手會越跑越累,所以一場好的馬拉松比賽會希望從一個休息站到下一個休息站的距離會越來越小。換句話說,如果馬拉松選手的路線是
$$a_1\rightarrow a_2\rightarrow ...\rightarrow a_k$$
且定義 $d_i$ 為連接編號 $a_i$ 城市到編號 $a_{i+1}$ 城市的路的長度,那
$$d_1\ge d_2 \ge ...\ge d_{k-1}$$

現在馬拉松主辦方想要舉辦一場好的馬拉松,所以提出了 $Q$ 個計畫,每個計畫是要辦一場編號 $A_i$ 的城市和編號 $B_i$ 的城市之間的馬拉松,但不確定是從編號$A_i$的城市到編號$B_i$的城市或是反方向,請告訴他們哪些計畫有可能舉辦出好的馬拉松比賽!

Input Format

輸入的第一行有兩個正整數 $N, Q$ ,代表接下來 $N$ 個城市還有 $Q$ 筆詢問。
接下來有 $N-1$ 行,每行有三個正整數 $u, v, d$ ,代表編號 $u, v$ 的城市中有一條長度為 $d$ 的馬路。
最後有 $Q$ 行,其中的第 $i$ 行有兩個正整數 $A_i, B_i$,代表第 $i$ 筆詢問的兩座城市。

  • $2\leq N\leq 10^ 5$
  • $1\leq Q\leq 10^ 5$
  • $1\leq u,v \leq N$
  • $u\neq v$
  • $1\leq d \leq 10^ 9$
  • $1\leq A_i,B_i \leq N$
  • $A_i\neq B_i$

輸入保證每座城市都恰有一條路徑達到另一個城市。

Output Format

請輸出 $Q$ 行。
第$i$行中,若可以舉辦一場城市編號為 $A_i,B_i$ 的馬拉松,則輸出YES,否則輸出NO

Sample Input

6 4
1 3 1
2 3 4
3 4 3
4 5 2
4 6 4
1 5
1 6
2 5
2 6

Sample Output

NO
YES
YES
NO

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~14 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 1
11 1000 65536 262144 1
12 1000 65536 262144 1
13 1000 65536 262144 1
14 1000 65536 262144 1