暴力做法 50 ~ 60
枚举删边，求最大路径长度的最小值。
其中最大路径长度运用到了lca
我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。
先把边按照权值排序，然后。。。
然而并没有什么卵用。
题解给出了一种二分
二分答案。
判断依据：
比当前答案大的路径长度如果有一个公共边，并且最大的路径减去这条公共边小于等于当前答案，那么当前答案就满足。
如果当前答案不满足，那么比他小的答案更不可能满足，因为都不小于等于当前答案，比当前答案小的更不可能。
接下来就是如何判断，num[i] 表示点 i 指向父亲的边被几条路径所共有。
那么只需要 num[x]++, num[y]++, num[lca(x, y)] -= 2
最后dfs一遍求树上前缀和即可。
然后在 (num[i] == 比当前答案大的边的条数) 中找最大的边
然后判断就可以了
但是就是一个点超时，无语，把倍增改成tarjan也是超时，蛋疼。
——代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MAXN 300001 int n, m, cnt, qcnt;
int num[MAXN], dis[MAXN], fv[MAXN], fa[MAXN], f[MAXN];
int head[MAXN], to[MAXN << ], val[MAXN << ], next[MAXN << ], qhead[MAXN], qnext[MAXN << ], qto[MAXN << ];
//int f[MAXN][21], deep[MAXN]; struct node
{
int qx, qy, lca, v;
}q[MAXN]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline void add(int x, int y, int z)
{
to[cnt] = y;
val[cnt] = z;
next[cnt] = head[x];
head[x] = cnt++;
} inline void addq(int x, int y)
{
qto[qcnt] = y;
qnext[qcnt] = qhead[x];
qhead[x] = qcnt++;
} /*inline void dfs(int u)
{
int i, v;
deep[u] = deep[f[u][0]] + 1;
for(i = 0; f[u][i]; i++) f[u][i + 1] = f[f[u][i]][i];
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(!deep[v]) fv[v] = val[i], dis[v] = dis[u] + val[i], f[v][0] = u, dfs(v);
}
} inline int Lca(int x, int y)
{
int i;
if(deep[x] < deep[y]) x ^= y ^= x ^= y;
for(i = 18; i >= 0; i--)
if(deep[f[x][i]] >= deep[y])
x = f[x][i];
if(x == y) return x;
for(i = 18; i >= 0; i--)
if(f[x][i] ^ f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}*/ inline int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
} inline void dfs(int u)
{
int i, v, x;
fa[u] = u;
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
if(f[u] ^ v) f[v] = u, dis[v] = dis[u] + val[i], fv[v] = val[i], dfs(v);
}
for(i = qhead[u]; i ^ -; i = qnext[i])
{
v = qto[i];
if(f[x = u ^ q[v].qx ^ q[v].qy] || x == ) q[v].lca = find(x);
}
fa[u] = f[u];
} inline void dfs1(int u)
{
int i, v;
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
if(v ^ f[u]) dfs1(v), num[u] += num[v];
}
} inline bool pd(int sum)
{
int i, x = , y = m, mid, ans, value = ;
memset(num, , sizeof(num));
while(x <= y)
{
mid = (x + y) >> ;
if(q[mid].v <= sum) x = mid + ;
else ans = mid, y = mid - ;
}
for(i = ans; i <= m; i++) num[q[i].qx]++, num[q[i].qy]++, num[q[i].lca] -= ;
dfs1();
for(i = ; i <= n; i++)
if(num[i] == m - ans + )
value = max(value, fv[i]);
if(!value) return ;
return q[m].v - value <= sum;
} inline bool cmp(node x, node y)
{
return x.v < y.v;
} int main()
{
int i, x, y, z, mid, ans = ;
n = read();
m = read();
memset(head, -, sizeof(head));
memset(qhead, -, sizeof(qhead));
for(i = ; i < n; i++)
{
x = read();
y = read();
z = read();
add(x, y, z);
add(y, x, z);
}
//dfs(1);
for(i = ; i <= m; i++)
{
q[i].qx = read();
q[i].qy = read();
addq(q[i].qx, i);
addq(q[i].qy, i);
//q[i].lca = Lca(q[i].qx, q[i].qy);
//q[i].v = dis[q[i].qx] + dis[q[i].qy] - (dis[q[i].lca] << 1);
}
dfs();
x = y = ;
for(i = ; i <= m; i++) q[i].v = dis[q[i].qx] + dis[q[i].qy] - (dis[q[i].lca] << ), y = max(y, q[i].v);
std::sort(q + , q + m + , cmp);
while(x <= y)
{
mid = (x + y) >> ;
if(pd(mid)) ans = mid, y = mid - ;
else x = mid + ;
}
printf("%d\n", ans);
return ;
}
还留有倍增的痕迹。