运输计划

发表于 分类于

Problem’s Website

运输计划

Solution

首先这是一道NOIP的压轴题。

题面好长啊，不少废话，一句话题意：

给定一棵树和m个任务（从$u$点到$v$点），可以使树上的一条边边权为0，让这m个任务中边权之和的最大值最小。

最大值最小? 那岂不是可以……

没错，我们可以二分答案。

那怎样检查答案的正确性呢？

我们不妨现将每个任务的权值和求出来，然后升序排序，如果当前的mid比最大值还大，那显然没有意义，在有意义的情况下，我们从小到大进行树上差分，最后枚举判断一下每一条边是否可以减少，判断一下如果修改后的最大值不大于当前mid,说明权值还可以缩小，否则就不能再缩小。

看到这，大家肯定有很多疑问，我们一一来解答

  1. 如何求每个任务的权值和？

权值和还是比较好求的，我们在树剖的第一个dfs中记录一下点到根中路径的权值和，那么公式为$dis[u] + dis[v] - 2 \times dis[LCA(u, v)]$,LCA我们不需要倍增求，直接用树剖记录的$top$数组求即可。

2.为什么要进行树上差分？

如果是一条满足条件的边修改为0，那么一定存在所有的其他需要修改的航道都经过了这条边（要不然他们就不会减少了）,所以要进行树上差分。

这道压轴题就愉快地AC了！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define pc(x) putchar(x)
#define re register
const int Maxn = 3e5 + 10;
inline int sc() {
	int xx = 0, ff = 1; char cch = gc;
	while(!isdigit(cch)) {
		if(cch == '-') ff = -1; cch = gc;
	}
	while(isdigit(cch)) {
		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
	}
	return xx * ff;
}
inline void out(int x) {
	if(x < 0) pc('-'), x = -x;
	if(x >= 10)
		out(x / 10);
	pc(x % 10 + '0');
}
struct node {
	int next, to, dis;
}t[Maxn << 1];
struct MAP {
	int u, v, d;
	bool operator < (const MAP &x) const {
		return d < x.d;
	}
}p[Maxn];
int n, m, cnt, l, r , ans;
int head[Maxn], fa[Maxn], son[Maxn], siz[Maxn], dep[Maxn], top[Maxn], id[Maxn], rid[Maxn], dis[Maxn], dfa[Maxn], cha[Maxn];
inline void ADD(int from, int to, int dis) {
	t[++cnt].next = head[from];
	t[cnt].to = to;
	t[cnt].dis = dis;
	head[from] = cnt;
}
inline void dfs1(int now, int Fa, int Dep) {
	fa[now] = Fa;
	dep[now] = Dep;
	siz[now] = 1;
	for(re int i = head[now]; i; i = t[i].next) {
		int to = t[i].to;
		if(to == Fa) continue;
		dfa[to] = t[i].dis;
		dis[to] = dis[now] + t[i].dis;
		dfs1(to, now, Dep + 1);
		siz[now] += siz[to];
		if(siz[son[now]] < siz[to])
			son[now] = to;
	}
}
inline void dfs2(int now, int topf) {
	id[now] = ++cnt;
	rid[cnt] = now;
	top[now] = topf;
	if(!son[now]) return;
	dfs2(son[now], topf);
	for(re int i = head[now]; i; i = t[i].next) {
		int to = t[i].to;
		if(to == son[now] || to == fa[now]) continue;
		dfs2(to, to);
	}
}
inline int LCA(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) std :: swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) std :: swap(x, y);
	return x;
}
inline void update(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) std :: swap(x, y);
		++cha[id[top[x]]];
		--cha[id[x] + 1];
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) std :: swap(x, y);
	--cha[id[y] + 1];
	++cha[id[x] + 1];
}
inline bool check(int x) {
	memset(cha, 0, sizeof(cha));
	int sum = 0, s = 0;
	if(p[m].d <= x) return 1;
	for(re int i = m; i >= 1; --i) {
		if(p[i].d <= x) break;
		++sum;
		update(p[i].u, p[i].v);
	}
	for(re int i = 1; i <= n; ++i) {
		s += cha[i];
		if(s == sum)
			if(p[m].d - dfa[rid[i]] <= x) return 1;
	}
	return 0;
}
int main() {
	n = sc(), m = sc();
	for(re int i = 1; i < n; ++i) {
		int x = sc(), y = sc(), z = sc();
		ADD(x, y, z), ADD(y, x, z);
	}
	cnt = 0;
	dfs1(1, 0, 1), dfs2(1, 1);
	for(re int i = 1; i <= m; ++i) {
		p[i].u = sc(), p[i].v = sc();
		p[i].d = dis[p[i].u] + dis[p[i].v] - (dis[LCA(p[i].u, p[i].v)] << 1);
		r = std :: max(r, p[i].d + 1); 
	}
	std :: sort(p + 1, p + m + 1);
	while(l <= r) {
		int mid = l + r >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	out(ans), pc('\n');
	return 0;
}
//Coded by dy.

rp++