https://gmoj.net/senior/#main/show/5051
Solution
首先注意到每個點有且只有一條出邊，也就是說這是一個環套樹（森林），
那么我們可以貪心，
首先這個森林里入度為零的點一定要跟root連邊，因為沒有任何其他的點可以到入度為零的點，然后就可以通過這些點更新其他的點，這個可以用拓撲來完成，
我們設dis陣串列示每個點到root的距離，在拓撲中，如果我們遇見了一個dis>k且入度為零的點,那么就將它和root連邊，
這樣子樹就處理完了，那么我們來考慮環，
不需要額外連邊的環可以先判掉，然后對于其他環上已經被更新過的點，先用它們去嘗試更新其他點，
那么問題就可以轉化為：現在有一個環，環上有一些點已經染了色，我們可以花費1的代價，將一條長為k的鏈上的點全部染色，要求代價最小，
這個問題的做法是：
先把環剖開，（長度為n的環變成長度為2n的線段），預處理出一個next陣列（表示一個點只經過染色點，最遠可以到達的點），
然后設f[i][j]表示第i個點，花費2j的代價，最遠能到達的點，我們可用next處理出f[i][0]，
然后從1~n每個點開始跳，求出最少跳幾次距離能>n，倍增優化跳躍，取min即可，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83475.html
標籤：其他