初見安～這裡是傳送門：洛谷P2680 運輸計劃
【懶到選擇截屏】
題解
一眼做不來【啪。】
所求是路徑最大值最小化。看到這種問法一眼二分，但是似乎二分并不好走，難點就在于讓哪條邊的邊權為0，也就是check函數怎麼寫。
那我們不妨把重心轉換一下。再回到二分的思路上來，我們二分答案，也就是最長的路徑長度，如果有路徑的長度大于我們二分的limit，那麼我們要化為0的邊必然在這條路徑上。換言之，我們要選擇的邊就是 衆多長度大于limit的路徑 的公共邊中的一條。
很顯然，我們當然是在公共邊裡面選最長的那一條了。
如果公共邊最長的一條的長度都小于最長的拿一條路徑和limit的內插補點，也就是說就算把這條最優的邊給指派成0也做不到在limit以内，不符合要求。反之，符合。
是以這個題說白了就是二分答案，然後标記公共邊，找最長的一個，check。
再細化，我們怎麼找公共邊？
假設我們有tot條路徑長度超過了limit，我們給這tot條路徑走過的邊都标記一次，那麼我們看圖上哪些邊被走過了tot次，就是這tot條邊的公共邊了。路徑覆寫，求次數——這不就是樹上差分了嘛~~邊化點差分一下，就可以找到所有的公共邊了。
總結——二分枚舉答案，
判定每條路徑的長度是否在limit以内，并差分标記，
周遊差分内容找公共邊，複雜度完全可行。
上代碼——【求路徑長度的部分，因為用樹剖求LCA但是又不想寫線段樹是以強行又差分了一下求dis
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 300005
using namespace std;
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
struct edge {int to, w, nxt;} e[maxn << 1];
int head[maxn], k = 0;
void add(int u, int v, int w) {e[k] = {v, w, head[u]}; head[u] = k++;}
int n, m;
int fa[maxn], dep[maxn], size[maxn], son[maxn], top[maxn], dis[maxn];
struct HLD {//封裝，樹剖求LCA
void dfs1(int u) {
size[u] = 1;
for(int i = head[u]; ~i; i = e[i].nxt) {
register int v = e[i].to; if(v == fa[u]) continue;
fa[v] = u; dep[v] = dep[u] + 1; dis[v] = dis[u] + e[i].w; //printf("fa[%d] = %d\n", v, u);
dfs1(v); size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
if(son[u]) dfs2(son[u], tp);
for(int i = head[u]; ~i; i = e[i].nxt) {
register int v = e[i].to;
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
int LCA(int u, int v) {
while(top[u] != top[v]) {
if(dep[top[u]] > dep[top[v]]) swap(u, v);
v = fa[top[v]];
}
if(dep[u] > dep[v]) return v; else return u;
}
}H;
int qu[maxn], qv[maxn], lca[maxn], len[maxn], cnt[maxn], max_num;
void solve(int u, int tot) {
for(int i = head[u]; ~i; i = e[i].nxt) {
register int v = e[i].to; if(v == fa[u]) continue;
solve(v, tot);
if(cnt[v] == tot) max_num = max(max_num, e[i].w);//這是一條公共邊了
cnt[u] += cnt[v];//樹上差分統計過程
}
}
bool check(int lim) {
memset(cnt, 0, sizeof cnt);
register int tot = 0, max_len = 0; max_num = 0;
for(int i = 1; i <= m; i++) if(len[i] > lim) {
max_len = max(max_len, len[i] - lim); tot++;//找最大內插補點
cnt[qu[i]]++, cnt[qv[i]]++, cnt[lca[i]] -= 2;//差分标記邊的覆寫次數【邊化點
}
solve(1, tot);
if(max_num >= max_len) return true;//如果最長公共邊都不能消除最大內插補點，就不行
else return false;
}
signed main() {
memset(head, -1, sizeof head);
n = read(), m = read();
for(int i = 1, u, v, w; i < n; i++) u = read(), v = read(), w = read(), add(u, v, w), add(v, u, w);
H.dfs1(1); H.dfs2(1, 1);
for(int u, v, i = 1; i <= m; i++) {
u = read(), v = read();
qu[i] = u, qv[i] = v;
lca[i] = H.LCA(u, v);
len[i] = dis[u] + dis[v] - 2 * dis[lca[i]];//dis差分，求len——路徑長度
}
register int l = 0, r = 5e8, mid, ans;// r的上界是3e8
while(l <= r) {
mid = l + r >> 1;
if(check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
迎評：）
——End——