CodeForces Round 805 pG2. Passable Paths  解題心得 ( 題目 )

解題概念:Heavy-Light Decompositon 

解題方法:題目要求的就是檢查集合他們是否在同個路徑，可以把他轉成要求樹上區間sum的問題(因為如果點全部在一條路徑上，就代表應該要有一組(x,y)他的那條路徑加起來等於集合點的數量，枚舉有O(N^2)個，但是因為樹的性質代表一個可以選最低點(dfs較深的)，枚舉變成N個，利用Heavy-Light Decompositon每次查詢為O(logNlogN)

Java solution code: 

https://wtools.io/paste-code/bDtG

 

 

 

 

 

 

 

arrow
arrow
    文章標籤
    Java 程式設計 解題心得 自主學習 Tree Heavy-Light Decompositon
    全站熱搜
    創作者介紹
    創作者 En Chi Tsung 的頭像
    En Chi Tsung

    阿祁的部落格

    En Chi Tsung 發表在 痞客邦 留言(0) 人氣()