传送门

暴力做法 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 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

还留有倍增的痕迹。