运输计划

题目就是询问将树上哪一条边的权重设为0之后，给定的m条路径的长度的最大值的最小。

我们先考虑序列上怎样做，再扩展到树上。我们先将边权转化为点权，对于最大值最小的问题，考虑二分答案。问题就转化为：是否存在一个数，权值为0之后，所有给定路径的长度和都小于等于mid（其实也就是最大值 (leq) mid）。对于一条路径，如果它的长度 > mid，那么一定要删除这条路径上的一条边，我们应该将这样的边设为0，即所有长度大于mid的路径的交集。差分就可以帮我们找出这样的边，可以用差分进行区间加的标记，看一看一条边的覆盖次数即可。

45分代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define x first
#define y second
using namespace std;

const int N = 3e5 + 100;

typedef pair<int, int> PII;
struct Edge {
	int v, w, nxt;
} e[ N << 1];
int n, m, cnt, head[N], seq[N], dis[N];
int sum[N], b[N];
PII p[N];

void AddEdge(int u, int v, int w) {
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

bool check(int mid) {
	int nums = 0, maxw = 0;
	for(int i = 1; i <= n; i ++)    b[i] = 0; 
	for(int i = 1; i <= m; i++) {
		int u = p[i].x, v = p[i].y;
		if( u > v)	swap(u, v);
		int d = sum[v - 1] - sum[u - 1];
		if(d > mid) {
			b[u] += 1, b[v] -= 1;
			nums ++;
			maxw = max(d, maxw);
		}
	}
	for(int i = 1; i <= n; i ++)
		b[i] = b[i] + b[i - 1];
	for(int i = 1; i < n; i ++) {
		if( b[i] == nums) {
			if( maxw - seq[i] <= mid)
				return true;
		}
	}
	return false;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i < n; i ++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		AddEdge(u, v, w), AddEdge(v, u, w);
		seq[i] = w;
	}
	for(int i = 1; i <= m; i ++) {
		scanf("%d%d", &p[i].x, &p[i].y);
	} 
	for(int i = 1; i <= n; i ++)
		sum[i] = sum[i - 1] + seq[i];
	int l = 0, r = 1e9;
	while(l < r) {
		int mid = (l + r) >> 1;
		if( check(mid))
			r = mid;
		else l = mid + 1;
	}
	printf("%d
", l);
	return 0;
}

对于树上的问题，我们只需要将前缀和转化为树上前缀和，差分转化为树上差分即可。

/*
统计将一条边的边权设为 0 之后的最大路径长度 
max( dist(u, v))

*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define x first
#define y second

using namespace std;

const int N = 3e5 + 100;
typedef pair<int, int> PII;

struct Edge {
	int v, w, nxt;
} e[ N << 1];

int n, m, cnt, head[N], dis[N], LCA[N], nums, maxw;
int dep[N], anc[N][22];
int sum[N], b[N];
PII p[N];
bool flag = false;

void dfs_lca(int u, int ff) {
	anc[u][0] = ff;
	dep[u] = dep[ff] + 1;
	for(int i = 1; i <= 20; i ++) 
		anc[u][i] = anc[anc[u][i - 1]][i - 1];
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if( ff == v)	continue;
		dfs_lca(v, u);
	} 
}


int lca(int u, int v) {
	if( dep[u] < dep[v]) swap(u, v);
	for(int i = 20; i >= 0; -- i) {
		if( dep[anc[u][i]] >= dep[v])
			u = anc[u][i];
	}
	if( u == v) return u;
	for(int i = 20; i >= 0; -- i) {
		if( anc[u][i] != anc[v][i])
			u = anc[u][i], v = anc[v][i];
	}
	return anc[u][0];
}

void AddEdge(int u, int v, int w) {
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

void dfs_df(int u, int fa) {
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if( v == fa)	continue;
		dfs_df(v, u);
		b[u] += b[v];
	}
}

void dfs_ans(int u, int ff, int mid) {
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if( v == ff)	continue;
		if(b[v] == nums)
			if( maxw - e[i].w <= mid)
				flag = true;
		dfs_ans(v, u, mid);
	}
}

bool check(int mid) {
	nums = 0, maxw = 0;
	for(int i = 1; i <= n; i ++)    b[i] = 0;
	for(int i = 1; i <= m; i++) {
		int u = p[i].x, v = p[i].y;
		if(dis[i] > mid) {
			b[u] += 1, b[v] += 1;
			b[LCA[i]] -= 2;
			nums ++;
			maxw = max(dis[i], maxw);
		}
	}
	dfs_df(1, 0);
	//进行一遍dfs，通过每条边的覆盖次数来统计答案
	flag = false;
	dfs_ans(1, 0, mid); 
	return flag;
}

void dfs_sum(int u, int fa) {
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if( v == fa)	continue;
		sum[v] = sum[u] + e[i].w;//错误1,回溯之前算 
		dfs_sum(v, u);
	}
}

void pre_dis() {
	for(int i = 1; i <= m; i ++) {
		int u = p[i].x, v = p[i].y;
		LCA[i] = lca(u, v);
		dis[i] = sum[u] + sum[v] - 2 * sum[LCA[i]];
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i < n; i ++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		AddEdge(u, v, w), AddEdge(v, u, w);
  	}
	for(int i = 1; i <= m; i ++) {
		scanf("%d%d", &p[i].x, &p[i].y);
	}
	dfs_lca(1, 0);//错误2：没有预处理 
	dfs_sum(1, 0);//树上前缀和 
	pre_dis();//树上两点间距离 
	int l = 0, r = 2e9;
	while(l < r) {
		int mid = (l + r) >> 1;
		if( check(mid))
			r = mid;
		else l = mid + 1;
	}
	printf("%d
", l);
	return 0;
}