[luoguP2680] 运输计划（lca + 二分 + 差分）

传送门

暴力做法 50 ~ 60

枚举删边，求最大路径长度的最小值。

其中最大路径长度运用到了lca

我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。

先把边按照权值排序，然后。。。

然而并没有什么卵用。

题解给出了一种二分

二分答案。

判断依据：

比当前答案大的路径长度如果有一个公共边，并且最大的路径减去这条公共边小于等于当前答案，那么当前答案就满足。

如果当前答案不满足，那么比他小的答案更不可能满足，因为都不小于等于当前答案，比当前答案小的更不可能。

接下来就是如何判断，num[i] 表示点 i 指向父亲的边被几条路径所共有。

那么只需要 num[x]++, num[y]++, num[lca(x, y)] = 2

最后dfs一遍求树上前缀和即可。

然后在 (num[i] == 比当前答案大的边的条数) 中找最大的边

然后判断就可以了

但是就是一个点超时，无语，把倍增改成tarjan也是超时，蛋疼。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 #define MAXN 300001 7 8 int n, m, cnt, qcnt; 9 int num[MAXN], dis[MAXN], fv[MAXN], fa[MAXN], f[MAXN]; 10 int head[MAXN], to[MAXN << 1], val[MAXN << 1], next[MAXN << 1], qhead[MAXN], qnext[MAXN << 1], qto[MAXN << 1]; 11 //int f[MAXN][21], deep[MAXN]; 12 13 struct node 14 q[MAXN]; 17 18 inline int read() 19 26 27 inline void add(int x, int y, int z) 28 34 35 inline void addq(int x, int y) 36 41 42 /*inline void dfs(int u) 43 52 } 53 54 inline int Lca(int x, int y) 55 */ 67 68 inline int find(int x) 69 72 73 inline void dfs(int u) 74 82 for(i = qhead[u]; i ^ 1; i = qnext[i]) 83 87 fa[u] = f[u]; 88 } 89 90 inline void dfs1(int u) 91 98 } 99 100 inline bool pd(int sum) 101 110 for(i = ans; i <= m; i++) num[q[i].qx]++, num[q[i].qy]++, num[q[i].lca] = 2; 111 dfs1(1); 112 for(i = 1; i <= n; i++) 113 if(num[i] == m ans + 1) 114 value = max(value, fv[i]); 115 if(!value) return 0; 116 return q[m].v value <= sum; 117 } 118 119 inline bool cmp(node x, node y) 120 123 124 int main() 125 139 //dfs(1); 140 for(i = 1; i <= m; i++) 141 149 dfs(1); 150 x = y = 0; 151 for(i = 1; i <= m; i++) q[i].v = dis[q[i].qx] + dis[q[i].qy] (dis[q[i].lca] << 1), y = max(y, q[i].v); 152 std::sort(q + 1, q + m + 1, cmp); 153 while(x <= y) 154 159 printf("%d\n", ans); 160 return 0; 161 }
View Code

还留有倍增的痕迹。

上一篇：[luoguP1507] NASA的食物计划（DP）

下一篇：网络流24题

---

stl 二分 lca dfs 差分 tarjan 倍增