运输计划 题解

给定一棵树以及树上的 $m$ 条通路，我们可以在树上选取一条边，将其权重置为 $0$，目标是

$$\ \ \ \ \ \ \ \ \ \ \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ min\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ max通路权重\\将某条边的权重重置0$$

20pts(m=1)

当 $m=1$ 时，我们只需要求出树上的一条链上的权重和与权重最大值即可。

50pts

考虑一种暴力的算法，枚举将哪一条边权重置 $0$，然后重新在树上求解 $m$ 条通路的权重。这个过程可以用 LCA 优化。任选一个结点为根，预处理出每一条通路的两个端点的 LCA，则路径长度可以通过树上差分快速计算。时间复杂度为 $O(n(n+m))$。

80pts(树退化为链)

当树退化为链时，这就是一个纯粹的数据结构问题。这类最小化最大值的问题可以考虑二分答案，将其转化为判定问题。给定一个权重上界 w ww 后，我们可以 O ( m ) O(m)O(m) 算出哪些通路的权重是超过这个上界的，而这些通路全部位于一条链上，因此我们可以 O ( m ) O(m)O(m) 求出它们的交集。然后在交集中找到权重最大的一条边，如果将这条边的权重置 $0$ 后，所有通路的权重均不超过 $w$，那么 $w$ 就是一个可行的上界。

100pts

上面的二分答案方法给了我们初步的思路。现在只需考虑树上给定权重上界后如何判定：首先任取一个结点作为根结点，并将边权下推为点权。使用差分维护数组 $f[v]$ 表示从 $v$ 的父结点到 $v$ 的这条边被经过了多少次。假设有 $cnt$ 个权重超过上届的通路，那么我们只要考虑被经过 $cnt$ 次的边即可。

AC代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10;

struct edge
{
	int v, w;
	int nxt;
} e[maxn << 1];
int n, m,
ver[maxn], w[maxn], a[maxn], b[maxn], c[maxn], d[maxn], f[maxn], s[maxn], num,
top[maxn], fa[maxn], size[maxn], son[maxn], dep[maxn], dis[maxn],
l, r, mid, ans, maxw;

inline void adde(int u, int v, int w)
{
	static int ed = 1;
	e[++ed] = (edge){ v, w, ver[u] };
	ver[u] = ed;
}

inline void dfs1(int u, int f)
{
	s[++num] = u;
	size[u] = 1, fa[u] = f;
	for(int i = ver[u]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		if(size[v])
			continue;
		dep[v] = dep[u] + 1;
		w[v] = e[i].w;
		dis[v] = dis[u] + w[v];
		dfs1(v, u);
		size[u] += size[v];
		if(size[son[u]] < size[v])
			son[u] = v;
	}
}

inline void dfs2(int u, int t)
{
	top[u] = t;
	if(son[u])
		dfs2(son[u], t);
	for(int i = ver[u]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		if(v == fa[u] || v == son[u])
			continue;
		dfs2(v, v);
	}
}

inline 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;
}

inline bool check(int k)
{
	memset(f, 0, sizeof f);
	int cnt = 0;
	for(int i = 1; i <= m; i++)
	{
		if(d[i] <= k)
			continue;
		f[a[i]]++, f[b[i]]++, f[c[i]] -= 2;
		cnt++;
	}
	for(int i = n; i >= 1; i--)
	{
		f[fa[s[i]]] += f[s[i]];
		if(w[s[i]] >= maxw - k && f[s[i]] == cnt)
			return true;
	}
	return false;
}

inline int read()
{
	static int x;
	static char c;
	x = 0, c = getchar();
	while(!isdigit(c))
		c = getchar();
	while(isdigit(c))
		x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x;
}

int main()
{
	n = read(), m = read();
	for(int i = 1; i < n; i++)
	{
		int u = read(), v = read(), w = read();
		adde(u, v, w);
		adde(v, u, w);
		l = max(l, w);
	}
	dep[1] = 1;
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1; i <= m; i++)
	{
		a[i] = read(), b[i] = read();
		c[i] = lca(a[i], b[i]);
		d[i] = dis[a[i]] + dis[b[i]] - (dis[c[i]] << 1);
		r = max(r, d[i]);
	}
	maxw = r, l = maxw - l, r++;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(check(mid))
			ans = mid, r = mid - 1;
		else
			l = mid + 1;
	}
	printf("%d", ans);
	return 0;
}