P2680 [NOIP 2015 提高组] 运输计划
大意
给你一棵树，一堆航线，航线之间有边权，让你输出最晚的航线最快啥时候到。
思路
首先就是最大值最小，我们可以考虑进行二分，二分答案 \(k\)，也就是说当前的所有航线的路程需要小于等于 \(k\)，我们知道，每次改完，最多能让一个航线的值减去 \(1\)，我们只需要判断这些大于等于 \(k\) 的航线交集最多的那条边即可。
于是我们的思路就出来了，二分 \(k\)，找交集最大的边，判断是否合法。
然后找交集的过程我们可以采用树上差分。
代码
#include<iostream>
#include<algorithm>
using namespace std;const int MAXN = 600005;
const int LOG = 19;int n, m;struct node{int to, nxt, len;
}e[MAXN];
int tot = 0, h[MAXN], dep[MAXN];
int d[MAXN], f[MAXN][LOG];
int sum[MAXN];
struct N{int u, v, val, lca;
}p[MAXN];
void add(int x, int y, int len){e[++ tot] = {y, h[x], len};h[x] = tot;
}void dfs(int u, int fa){dep[u] = dep[fa] + 1;f[u][0] = fa;for(int i = h[u];i;i = e[i].nxt){int v = e[i].to;if(v == fa) continue;sum[v] = sum[u] + e[i].len;dfs(v, u);}
}void I_nt(){for(int k = 1;k < LOG;k ++){for(int i = 1;i <= n;i ++){f[i][k] = f[f[i][k - 1]][k - 1];}}
}int LCA(int u, int v){if(dep[u] < dep[v]) swap(u, v);for(int k = LOG - 1;k >= 0;k --){if(dep[f[u][k]] >= dep[v]){u = f[u][k];}}if(u == v) return u;for(int k = LOG - 1;k >= 0;k --){if(f[u][k] != f[v][k]){u = f[u][k];v = f[v][k];}}return f[u][0];
}int tmp, ans;void dfs2(int u, int fa){for(int i = h[u];i;i = e[i].nxt){int v = e[i].to;if(v == fa) continue;dfs2(v, u);d[u] += d[v];}if(d[u] == tmp){ans = max(ans, sum[u] - sum[f[u][0]]);}
}bool check(int mid){for(int i = 1;i <= n;i ++) d[i] = 0;tmp = 0;for(int i = 1;i <= m;i ++){if(p[i].val > mid){tmp ++;d[p[i].u] ++;d[p[i].v] ++;d[p[i].lca] -= 2;}else break;}ans = -1e9;dfs2(1, 0);if(p[1].val - ans > mid){return false;}return true;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for(int i = 1;i < n;i ++){int u, v, w; cin >> u >> v >> w;add(u, v, w), add(v, u, w);}dfs(1, 0);I_nt();int l = 0, r = 0;for(int i = 1;i <= m;i ++){cin >> p[i].u >> p[i].v;p[i].lca = LCA(p[i].u, p[i].v);p[i].val = (sum[p[i].u] + sum[p[i].v] - 2 * sum[p[i].lca]);r = max(r, p[i].val);}sort(p + 1, p + m + 1, [](N a, N b){return a.val > b.val;});while(l <= r){int mid = (l & r) + ((l ^ r) >> 1);if(check(mid)){//mid is okr = mid - 1;}else{l = mid + 1;}}cout << l << '\n';return 0;
}