洛谷 P2680 运输计划 树链剖分+LCA+树上差分+二分

洛谷 P2680 运输计划

题意

• 给你一个 $n$ 个点的树,对于 $n-1$ 条边各有边权,
• 给出一些点对 $(x,y)$ ,同时定义 $dis(x,y)$ 表示 $x,y$ 两点间的树上距离,
• 现允许你将一条边的权值变为 $0$ ,请你最小化最大的 $dis(x,y)$ 的值。

解法

为了使最长路径最短，考虑二分答案。

那么如何判断 $mid$ 值是否可行呢。我们可以求出每一条路径的距离，如果这个距离大于 $mid$ ，就可以肯定删掉的那条边一定在这个路径上。那么可以发现，选择修改边权的那一条边一定是所有路径长度大于 $mid$ 的路径的交集。树上边差分来判断这条边（边的深度较大的结点）是否等于 $cnt$ （$cnt$ 表示距离大于 $mid$ 的路径个数），如果等于 $cnt$ 且 $maxx(最长路径)-val(这条边的权值)\le mid$ ，则这个$mid$ 是可行的。

求树上路径的距离，可以用树上前缀和处理，即 $dis(u,v)=dis(r,u)+dis(r,v)-2\ast dis(r,lca(u,v))$ 。 $lca$ 可以用树链剖分来求，顺便在第一次dfs的时候维护出每一个结点到父亲的距离和dfs序。

判断某条边被访问的次数，用树上差分来处理。

代码

#pragma region
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
#pragma endregion
const int maxn = 3e5 + 5;
int n, m;
vector<pair<int, int>> g[maxn];
int fa[maxn], son[maxn], sz[maxn], dep[maxn];
int cnt, top[maxn];
int dnf[maxn], tot;
//dfs序
int dis[maxn], val[maxn];
void dfs1(int u, int f, int deep) {
fa[u] = f, sz[u] = 1, dep[u] = deep;
dnf[++tot] = u;
for (auto e : g[u]) {
int v = e.first, w = e.second;
if (v == f) continue;
val[v] = w;
dis[v] = dis[u] + w;
dfs1(v, u, deep + 1);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int topf) {
top[u] = topf;
if (!son[u]) return;
dfs2(son[u], topf);
for (auto e : g[u]) {
int v = e.first;
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int Lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
struct node {
int u, v, lca, d;
} A[maxn];
int c[maxn];
bool check(int mid) {
memset(c, 0, sizeof(c));
int cnt_ = 0, maxx = 0;
rep(i, 1, m) {
if (A[i].d > mid) {
maxx = max(maxx, A[i].d);
c[A[i].u]++, c[A[i].v]++;
c[A[i].lca] -= 2;
cnt_++;
}
}
for (int i = n; i >= 1; --i) {
c[fa[dnf[i]]] += c[dnf[i]];
if (c[dnf[i]] == cnt_ && maxx - val[dnf[i]] <= mid) return 1;
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n - 1) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs1(1, 0, 1);
dfs2(1, 1);
rep(i, 1, m) {
scanf("%d%d", &A[i].u, &A[i].v);
A[i].lca = Lca(A[i].u, A[i].v);
A[i].d = dis[A[i].u] + dis[A[i].v] - 2 * dis[A[i].lca];
}
int l = 0, r = 1e9;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
printf("%dn", r);
}

最后

以上就是忧心猫咪为你收集整理的洛谷 P2680 运输计划 树链剖分+LCA+树上差分+二分的全部内容，希望文章能够帮你解决洛谷 P2680 运输计划 树链剖分+LCA+树上差分+二分所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。