transport plan

Title Link: ybt high efficiency advanced 4-5-5 / luogu P2680

General idea of the topic

There is a tree with weights on its edges.
Then there are some paths, and then you can choose an edge and make its weight become 0.
If you want to make the modified longest given path the shortest, output this value.

thinking

First, when you see the distance of the path on the required tree, you will think of LCA first.

But it can change the weight.
Then let's start from the aspect of the longest path and the shortest, and think of the length of two.
The left boundary is naturally the longest path minus the longest edge, and the right boundary is the longest path.

With this length, we will find that the length of some paths is greater than it. That is to say, in order for this length to be the longest, the path larger than it must have an edge in the middle with the weight changed, and after the change, it must be under this weight.

Then we have a general idea. We find the paths that are just longer than. Then find the edges in the tree. All these paths pass through it, and then choose the one with the largest weight. Then judge whether the path with the longest length minus it is below the requirement.

Then the new problem arises again. How to find the edge of satisfaction.
We can choose to count the number of occurrences of edges. If the number of occurrences is equal to the number of paths, it is the satisfied edge.

Then we think, for a path, it is a chain on the tree, so you have to add one to all the edges of a chain on the tree.
It's a bit like adding one to the interval. Naturally, it's thought of the difference on the tree. Then you can split the chain into two with LCA, and then add them respectively.
Then add a dfs to restore the difference sequence.

That's it.

code

#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) {//Preprocessing to be used for multiplication
	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) {//Find LCA (by the way, find the distance of the path)
	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) {//Difference
	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];//Restore difference tree
		}
}

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);//Take the original chain apart and multiply it by two, which is convenient for adding
		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) {//Find whether there are any edges that can be reduced, and select the one with the largest weight
			maxn = max(maxn, dis[0][i]);
		}
	
	return q[1].dis - maxn <= mid;//See if it can be reduced below the required time
}

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++)//Multiplication 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++) {//Information recorded for each path
		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);//Sort paths by length from large to small
	
	while (l <= r) {//Half the final length
		mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	
	printf("%d", ans);
	
	return 0;
}