Luogu P2680 [NOIP2015 提高组] 运输计划
题意：
一个 \(n\) 个节点的树 ,每条路有通过时间 \(t[i]\) ，有 \(m\) 条路线 ,将一条路的 \(t[i]\) 值变为0，让最大的路线时间最小。
思路：
求解转判定 ，二分答案 ,每次判断这个限制能不能满足。
找最大的 公共的 不合法的 路 \(R\) （因为要让所有路线满足限制，所以让最大的公共的不合法的路为0）,若将路 \(R\) 的 \(t[i]\) 为0，使所有路线满足限制 ,那这个限制就是可以的。
PS:使最大值最小 、最小值最大 的问题很多都是求解转判定 qwq 。
那大致思路有了 ,那如何求最大公共不合法路？ 直接遍历总复杂度 \(O(n^2logn)\) ，这个 \(logn\) 是二分的 ,最大能到28左右 ,要优化。
其实优化一般就这几种 \(↓\)
- 1.所有操作统一到一起计算。
- 2.预处理些东西。
- 3.把式子化简。
- 4.转换成等价但好算的东西。（讲的挺模糊的，以后找题挂上来 如：CF1473E
$\ $
很明显 ,考虑优化遍历找公共路。（其他都优化不了吧 qwq ）
我选 第一种优化。我们可以差分找出上文那个 \(R\) ,我选 树上点差分。
简单介绍一下树上点差分 ： \(point[i]\) 表示 \(1\) ~ \(i\) 都要加 \(point[i]\) 个点 ,要标记出 \(u\) ~ \(v\) 有条路 ,那就
point[u]++; point[v]++; point[lca(u,v)]--; if(lca(u,v)!=root)fa[lca(u,v)]--;
画图很好理解的 。LCA我个人主页里模板栏里也有点介绍
所以 ,流程就是：
- 二分找最小限制。
- 树上差分找 \(R\) 。
- 最大路线耗时 - \(R\) 的 \(t[i]\) 值 \(\le\) \(limit\) ,就满足条件。
$\ $
超时如何解决?
- 按这种思路 ,我认为一定要将递归换成循环 ,递归慢的一批 qwq 。
- \(\operatorname{lca}\) 可以预处理，因为只需要 \(m\) 个。
按我的习惯 ,一般是将些 细节、易错点 放代码注释里的 ,我想会有帮助（对初学者而言
//By - JT Time - 2023.7.21~2023.7.22
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n, m, go[N][21], u[N], v[N], dep[N], bad_point, LCA[N], lg;
int point[N];//c边的前缀和 point点的前缀和
int maxn, maxr, c[N], dis[N];
struct edge {
int to;
int w;
};
vector<edge> g[N];
inline int read() {
int s = 0, f = 1; char c = getchar();
while (c < '0' || c>'9') { if (c == '-')f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { s = (s << 3) + (s << 1) + (c ^ 48); c = getchar(); }
return s * f;
}
int Log(int x) {
int p = 1, cnt = 0;
while (2 * p <= x)p *= 2, cnt++;
return cnt;
}
void dfs_depth(int x, int fa) {
dep[x] = dep[fa] + 1;
go[x][0] = fa;
for (int i = 0; i < g[x].size(); i++) {
int t = g[x][i].to;
if (t == fa)continue;
c[t] = c[x] + g[x][i].w; //先更新再传递，下一层要用这一层的前缀和
dfs_depth(t, x);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y])swap(x, y);
//先让x为深度大的点
for (int i = lg; i >= 0; i--)if (dep[go[x][i]] > dep[y])x = go[x][i];
//先跳到统一深度，那么以后总能跳到同一点
if (dep[x] != dep[y])x = go[x][0];
//如果不在同一深度,再跳一步到同一点,go[x][0]表示再x点跳2^0=1步
for (int i = lg; i >= 0; i--)if (go[x][i] != go[y][i])x = go[x][i], y = go[y][i];
//先别跳到一起，倍增思想(找最近的不在一起的，所以只要再跳一次就到同一点了)
if (x == y)return x;
//如果正好在同一点就不跳,go[x][0]表示再x点跳2^0=1步
return go[x][0];
}
void dfs_point(int x, int fa) {
for (int i = 0; i < g[x].size(); i++) {
int t = g[x][i].to;
if (t == fa)continue;
dfs_point(t, x);
point[x] += point[t];
}
}
bool check(int lim) {
memset(point, 0, sizeof(point));
maxn = 0, maxr = 0, bad_point = 0; //maxn 是所有不符合计划都重合的边 的边权最大值，maxr 是不符合计划的最大总长
for (int i = 1; i <= m; i++) {
//点上差分，是减一次lca() 和 减一次fa[lca()] ,不同于边上的减两次lca() 画图理解
if (dis[i] <= lim)continue; //只有不符合条件的加入
bad_point++;
point[u[i]]++;
point[v[i]]++;
point[LCA[i]]--;
if (LCA[i] != 1)point[go[LCA[i]][0]]--;
maxr = max(maxr, dis[i]);
}
dfs_point(1, 0);
for (int i = 1; i <= n; i++)
for (int j = 0; j < g[i].size(); j++)
if (point[i] == bad_point && point[g[i][j].to] == bad_point)maxn = max(maxn, g[i][j].w);
//★不能在传点的时候就统计，假如u有2儿子v1 v2, 计划是从v1->v2 ,则point[u]=-1 ,point[v1]=1 ,point[v2]=1 ,传点时先走v1 ,point[u]=0,但bad_point=1 ,所以不会被统计
/*
一开始的代码的反例 :
in:
3 1
1 3 2
1 2 3
2 3
out:
3（Wrong Answer）
in: (只有权值调换位置
3 1
1 3 3
1 2 2
2 3
out:
2 (Accepted)
*/
return (maxr - maxn <= lim); //删掉最大公共不合法边后，合不合法
}
int main() {
n = read(), m = read();
lg = Log(n);
for (int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
g[u].push_back(edge{ v,w });
g[v].push_back(edge{ u,w });
}
dfs_depth(1, 1);
for (int t = 1; t <= lg; t++)
for (int i = 1; i <= n; i++)
go[i][t] = go[go[i][t - 1]][t - 1];
int l = 0, r = 0; //二分要优化
for (int i = 1; i <= m; i++) {
u[i] = read(), v[i] = read();
LCA[i] = lca(u[i], v[i]);
dis[i] = c[u[i]] + c[v[i]] - 2 * c[LCA[i]], r = max(r, dis[i]);
}
while (l < r) {
int mid = (l + r) / 2;
if (check(mid))r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}