BZOJ 4326

題意

給你一棵樹和邊權，有若干條航線，從樹上的一個點到另一個點。令運輸時間為所有航線所需要的時間中的最長時間。你可以將某一條邊的權值變為0，求這個最長時間的最小值。

樣例輸入

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

樣例輸出

11

SOL

先講一下部分分畢竟這是一道聯賽題。 1、首先想到就是預處理lca，然后枚舉變為0的邊計算每條航線的權值，時間復雜度為n^2，可以過掉10個點。 2、考慮到m=1只有一條航線，直接找鏈上的最大值即可，這又有2個點。 3、對于單鏈的情況，首先這個題目的問法就是讓你二分答案。然后我們考慮如何check一個答案。我們假設check的答案為x，預處理每條航線的長度，然后把所有大于x的航線全部放到單鏈上，如果存在這樣一條邊，使得所有大于x的航線都經過，并且最長的航線減去這條邊的權值小于等于x，這就意味著如果把這條邊的權值變為0，所有的航線長度都是小于等于x的，那么這個x就是可行的。這里“把所有大于x的航線全部放到單鏈上”用到了差分的方法，每次只要對起點和終點操作，時間復雜度為nlogn。這樣可以過掉8個點。 結合1、2、3可以過掉16個點。 4、其實上面已經說了單鏈的做法，那么只要對樹剖分一下就可以滿分了。最后一個點略微卡常，我用了讀入優化后在bzoj和uoj上都是跑得過去的，不過ccf的老爺機聽說要被卡掉一個點。

代碼