P2680 [NOIP2015 提高组] 运输计划

P2680 [NOIP2015 提高组] 运输计划

给定一棵边带权的树，以及 \(m\) 条路径，可以将某条边的边权变为 \(0\)，求最大路径和的最小值。

一开始看错题了，导致一度认为是水题，但是更正题意后发现其实就套了个二分。

最大值最小想到二分答案，判定的时候直接树上差分，找到经过所有 \(>mid\) 的路径的边中边权最大的。

然后用最大路径和 - 边权来判断即可，这个思想比较巧妙，因为最大的满足了，其它一定也满足。

#include
#include
#include
using namespace std;

typedef long long LL;
const int N = 300010;
int n, m, cnt, num, mxp; LL len, dis[N];
int head[N], d[N], dep[N], fa[N][30];
struct Edge{int nxt, to, val;} ed[N << 1];
struct Modify{int x, y; LL dis;} a[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

void add(int u, int v, int w){
	ed[++ cnt] = (Edge){head[u], v, w};
	head[u] = cnt;
}

void dfs1(int u, int Fa){
	dep[u] = dep[Fa] + 1; fa[u][0] = Fa;
	for(int i = 1; (1 << i) <= dep[u]; i ++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(int i = head[u], v; i; i = ed[i].nxt)
		if((v = ed[i].to) != Fa){
			dis[v] = dis[u] + ed[i].val;
			dfs1(v, u);
		}
}

int Lca(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	for(int i = 20; i >= 0; i --)
		if(dep[fa[y][i]] >= dep[x]) y= fa[y][i];
	if(x == y) return x;
	for(int i = 20; i >= 0; i --)
		if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

void dfs2(int u, int Fa){
	for(int i = head[u]; i; i = ed[i].nxt){
		int v = ed[i].to, w = ed[i].val;
		if(v == Fa) continue;
		dfs2(v, u); d[u] += d[v];
		if(d[v] == num) mxp = max(mxp, w);
	}
}

bool chck(LL mid){
	for(int i = 1; i <= n; i ++) d[i] = 0;
	mxp = 0, num = 0;
	for(int i = 1; i <= m; i ++)
		if(a[i].dis > mid){
			num ++; int x = a[i].x, y = a[i].y;
			d[x] ++, d[y] ++, d[Lca(x, y)] -= 2;
		}
	dfs2(1, 0);
	return (len - mxp <= mid);
}

int main(){
	n = read(), m = read();
	for(int i = 1; i < n; i ++){
		int u = read(), v = read(), w = read();
		add(u, v, w), add(v, u, w);
	}
	dfs1(1, 0);
	LL l = 0, r = 0;
	for(int i = 1; i <= m; i ++){
		int u = read(), v = read();
		LL w = 1LL * dis[u] + dis[v] - 2LL * dis[Lca(u, v)];
		a[i] = (Modify){u, v, w}; r = max(r, w);
	}
	len = r;
	while(l < r){
		LL mid = (l + r) >> 1;
		if(chck(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%lld\n", l);
	return 0;
}