P2680题目的大意就是走完m条路径所需要的最短时间（边权是时间），其中我们可以把一条边的权值变成0（也就是题目所说的虫洞） 。
可以考虑二分答案x，找到一条边，使得所有大于x的路径都经过这条边（差分维护），并且路径减去这条边的边权后小等于x，通过这样判定x是否可行 。
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 3e5 + 10; 5 int tot, head[N], to[N << 1], nxt[N << 1], edge[N << 1]; 6 int n, m, fa[N][25], dep[N], dis[N], pre[N], num[N]; 7 struct node { 8int x, y, lca; 9 }q[N];10 void add(int x, int y, int z) {11nxt[++ tot] = head[x], head[x] = tot, to[tot] = y, edge[tot] = z;12 }13 void dfs(int u, int f) {14dep[u] = dep[f] + 1;15fa[u][0] = f;16for (int i = 1; i <= 20; i ++)17fa[u][i] = fa[fa[u][i - 1]][i - 1];18for (int i = head[u]; i; i = nxt[i]) {19int v = to[i];20if (v == f) continue;21pre[v] = edge[i];//v所在这条边的边权22dis[v] = dis[u] + edge[i];23dfs(v, u);24}25 }26 int getlca(int x, int y) {27if (dep[x] < dep[y]) swap(x, y);28for (int i = 20; i >= 0; i --) {29if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];30}31if (x == y) return x;32for (int i = 20; i >= 0; i --) {33if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];34}35return fa[x][0];36 }37 int flag, cnt, maxn;38 int judge(int u, int f, int cnt, int maxn) {//返回子树和39int k = num[u];40for (int i = head[u]; i; i = nxt[i]) {41int v = to[i];42if (v == f) continue;43k += judge(v, u, cnt, maxn);44}45if (k >= cnt && pre[u] >= maxn) flag = 1;46//所有>mid的边都经过u所在这条边i，且i的权值满足条件47return k;48 }49 bool check(ll mid) {50memset(num, 0, sizeof num);51maxn = cnt = flag = 0;52for (int i = 1; i <= m; i ++) {53int d = dis[q[i].x] + dis[q[i].y] - 2 * dis[q[i].lca];54if (d > mid) {55num[q[i].x] ++, num[q[i].y] ++, num[q[i].lca] -= 2;56cnt ++;57maxn = max(maxn, d);58}59}60if (!cnt) return 1; // !!!!!61judge(1, 0, cnt, maxn - mid);62return flag;63 }64 int main() {65scanf("%d %d", &n, &m);66for (int i = 1; i < n; i ++) {67int a, b, c;68scanf("%d %d %d", &a, &b, &c);69add(a, b, c), add(b, a, c);70}71dfs(1, 0);72for (int i = 1; i <= m; i ++) {73scanf("%d %d", &q[i].x, &q[i].y);74q[i].lca = getlca(q[i].x, q[i].y);75}76ll l = 0, r = 300000000;77while (l < r) {78ll mid = (l + r) >> 1;79if (check(mid)) r = mid;80else l = mid + 1;81}82printf("%lld\n", l);83return 0;84 } 【树上差分-边差分 P2680 [NOIP2015 提高组] 运输计划】
经验总结扩展阅读
- 中国边界线有多少公里?
- 笔记本电脑图标在右边怎么弄
- 平分线分对边是什么意思
- 懵逼树上懵逼果逼树下你和我是什么意思?
- 阔腿裤翻边方法
- 苹果5s通用里边的型号什么意思
- 微信的朋友圈的头像旁边有个圆圈是什么意思？
- 高架边的房子有什么利弊
- 井口为什么是六边形
- 为什么周边叫谷子