【ybt高效进阶4-5-5】【luogu P2680】运输计划

运输计划

题目链接：ybt高效进阶4-5-5 / luogu P2680

题目大意

有一个树，边有权值。

然后有一些路径，然后你可以选一条边，使它的权值变成 0。

要你让修改后最长的给出路径最短，输出这个值。

思路

首先看到要求树上路径的距离，先会想到 LCA。

但是它可以改变权值。

那我们就从最长路径最短这个方面下手，想到二分这个长度。

那左边界自然就是最长的路径减去最长的边，右边界就是最长的路径。

那有了这个长度，我们会发现有一些路径的长度是大于它的。那也就是说，为了让这个长度是最长的，大于它的路径必须中间有一条边是改权值的，而且改了之后还要在这个权值之下。

那大概的思路就有了，我们找到刚刚那些长度超过的路径。然后在树上找有哪些边所有这些路径都经过了它，然后选权值最大的一条。然后再判断一下长度最长的路径减去它是否在要求以下。

那新的问题又出现了，如何找满足的边呢。

我们可以选择统计边的出现次数，如果这个出现次数就等于那些路径的个数的话，就是满足的边。

那我们想，对于一条路径，它就是树上的一条链，那你要把树上一条链上的边都加一。

那有点类似区间加一，自然想到树上差分，那你就把链用 LCA 拆成两个，然后分别加。

然后加完之后一个 dfs 还原一下差分序列，就可以了。

那就是这样的了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> 

using namespace std;

struct node {
	int x, to, nxt;
}e[600001];
struct quest {
	int x, y, lca, dis;
}q[300001];
int n, m, x, y, z, le[300001], KK;
int fa[21][300001], dis[21][300001], deg[300001];
int l, r, ans, mid, val[300001], nn;

void add(int x, int y, int z) {
	e[++KK] = (node){z, y, le[x]}; le[x] = KK;
}

void dfs(int now, int father) {//倍增要用的预处理
	fa[0][now] = father;
	deg[now] = deg[father] + 1;
	
	for (int i = le[now]; i; i = e[i].nxt)
		if (e[i].to != father) {
			dfs(e[i].to, now);
			dis[0][e[i].to] = e[i].x;
		}
}

int LCA(int x, int y, int pl) {//求 LCA（顺便求出了路径的距离）
	if (deg[y] > deg[x]) swap(x, y);
	for (int i = 20; i >= 0; i--)
		if (deg[fa[i][x]] >= deg[y]) {
			q[pl].dis += dis[i][x];
			x = fa[i][x];
		}
	if (x == y) return x;
	for (int i = 20; i >= 0; i--)
		if (fa[i][x] != fa[i][y]) {
			q[pl].dis += dis[i][x] + dis[i][y];
			x = fa[i][x];
			y = fa[i][y];
		}
	q[pl].dis += dis[0][x] + dis[0][y];
	return fa[0][x];
}

bool cmp(quest x, quest y) {
	return x.dis > y.dis;
}

void add_line(int s, int t) {//差分
	val[t]++;
	val[s]--;
}

void dfs_cf(int now, int father) {
	for (int i = le[now]; i; i = e[i].nxt)
		if (e[i].to != father) {
			dfs_cf(e[i].to, now);
			val[now] += val[e[i].to];//还原差分树
		}
}

bool check(int now) {
	nn = 0;
	memset(val, 0, sizeof(val));
	for (int i = 1; i <= m; i++) {
		if (q[i].dis <= now) break;
		add_line(q[i].lca, q[i].x);//把原来的链拆开乘两条，方便加
		add_line(q[i].lca, q[i].y);
		nn++;
	}
	
	dfs_cf(1, 0);
	
	int maxn = 0;
	for (int i = 1; i <= n; i++)
		if (val[i] == nn) {//找有没有都可以减的边，选权值最大的减
			maxn = max(maxn, dis[0][i]);
		}
	
	return q[1].dis - maxn <= mid;//看能不能减到要求的时间以下
}

int main() {
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i < n; i++) {
		scanf("%d %d %d", &x, &y, &z);
		add(x, y, z);
		add(y, x, z);
		l = max(l, z);
	}
	
	dfs(1, 0);
	for (int i = 1; i <= 20; i++)//倍增LCA
		for (int j = 1; j <= n; j++) {
			fa[i][j] = fa[i - 1][fa[i - 1][j]];
			dis[i][j] = dis[i - 1][j] + dis[i - 1][fa[i - 1][j]];
		}
	
	for (int i = 1; i <= m; i++) {//记录每条路径的信息
		scanf("%d %d", &q[i].x, &q[i].y);
		q[i].lca = LCA(q[i].x, q[i].y, i);
		r = max(r, q[i].dis);
	}
	l = r - l;
	
	sort(q + 1, q + m + 1, cmp);//把路径按长度从大到小排序
	
	while (l <= r) {//二分最后的长度
		mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	
	printf("%d", ans);
	
	return 0;
}