主唱太拼命了
現在給定一個 N 個節點的樹,由 N−1 條邊連接,第 i 條邊連接點 ui 與 vi,且邊上有一顆種類 ki 的堅果。
請回答 Q 筆詢問,每次詢問會給定 si,ti,現在考慮從 si 出發、用最短路徑走到 ti 的路徑,並收集所有路徑上的堅果。假設對於種類 x 的堅果我們收集到了 Cx 個,請問有多少堅果種類對 (a,b),滿足 Ca>0,Cb>0,Ca×2=Cb?注意到每筆詢問是獨立的,每次詢問收集完後會再將堅果放回去。
輸入第一行有兩個正整數 N,Q,分別代表樹的大小與詢問的數量。
接下來 N−1 行每行有三個正整數 ui,vi,ki,代表有一條從 ui 到 vi 的無向邊,這條邊上面有一顆種類 ki 的堅果。
接下來 Q 行每行有兩個正整數 si,ti,代表詢問的兩個參數。
輸出 Q 行,第 i 行上有一個整數代表第 i 筆詢問的答案。
IOICamp 2020 Day2 pG