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