NOIP2015 Day2 T3(树上差分序列+LCA)

这题求最大值最小,显然二分。
我们二分本题的答案,如何处理虫洞的情况?
因为只能改造一个虫洞,那么这个虫洞一定是在某些“不改造虫洞会超过二分答案的路径”上,也就是这些路径的交。
那么我们先把每条路径的时间长求出来,怎么求?树上的路径,用LCA即可,时间复杂度$O(mlogn)$
求出来以后,我们每次二分,都一一检查每个路径的时间,如果大于二分答案,就在树上将这一个路径覆盖,那么问题来了,这里怎么覆盖?直接暴力?$O(mn)$的时间复杂度无法接受。这里方法一是树剖后线段树维护,但是这样的代码量直线上升。我们可以考虑差分序列。在线性的数据结构上的差分序列我们已经很熟悉了,$f[a]+1$, $f[b+1]-1$,那么在树上怎么办?很简单,我们让$f[u]+1, f[v]+1, f[LCA(u, v)]-2$,这样做以后在树上的前缀和$\sum_{k\in son(i)}{f[k]}$就表示该点为到其父亲的这条边被经过的次数,之后再找出所有路径的交,判定一下删除的情况就行了,这个地方边权一定要转化为点权。修改在深度深的那个节点上,否则会出现节点未更新完就判断导致错误,代码中有提示。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 300000 + 5, logs = 21, INF = 1000000000;
int n, m, en, dep[MAXN], fa[MAXN], pre[MAXN][logs+1], dis[MAXN], pu[MAXN], pv[MAXN],
pc[MAXN], f[MAXN], lca[MAXN], dwi[MAXN];
vector<int> G[MAXN];
struct edge{int v, wi;}e[MAXN*2];
void ins(int u, int v, int wi) {
en++, e[en].v = v, e[en].wi = wi, G[u].push_back(en);
}
void clean() {
en = 0;
for (int i=0;i<=n;i++) {
G[i].clear();
lca[i] = pc[i] = dep[i] = fa[i] = dis[i] = 0;
for (int j=0;j<=logs;j++) pre[i][j] = 0;
}
}
void init() {
clean();
for (int i=1;i<n;i++) {
int ai, bi, ti;
scanf("%d%d%d", &ai, &bi, &ti);
ins(ai, bi, ti), ins(bi, ai, ti);
}
for (int i=1;i<=m;i++) {
scanf("%d%d", &pu[i], &pv[i]);
}
}
void dfs1(int u, int pa) {
dep[u] = dep[pa]+1, fa[u] = pa, pre[u][0] = pa;
for (int i=1;i<=logs;i++) pre[u][i] = pre[pre[u][i-1]][i-1];
for (int i=0;i<G[u].size();i++) {
edge ed = e[G[u][i]];
int v = ed.v, wi = ed.wi;
if (v!=pa) {
dis[v] = dis[u] + wi;
dwi[v] = wi;
dfs1(v, u);
}
}
}
int LCA(int a, int b) {
if (dep[a]<dep[b]) swap(a, b);
for (int i=logs;i>=0;i--) if (dep[pre[a][i]]>=dep[b]) a = pre[a][i];
if (a==b) return a;
for (int i=logs;i>=0;i--) if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
int max1, max2, tot;
void dfs2(int u, int pa) {
for (int i=0;i<G[u].size();i++) {
edge ed = e[G[u][i]];
int v = ed.v, wi = ed.wi;
if (v!=pa) {
dfs2(v, u);
f[u] += f[v];
}
}
if (f[u]==tot) max2 = max(max2, dwi[u]);
}
bool check(int x) {
ms(f, 0), tot = max1 = max2 = 0;
for (int i=1;i<=m;i++) {
if (pc[i]>x) {
max1 = max(max1, pc[i]);
tot++;
f[lca[i]]-=2;
f[pu[i]]++, f[pv[i]]++;
}
}
dfs2(1, 0);
return x>=max1-max2;
}
void solve() {
dfs1(1, 0);
int l = 0, r = 300000*1000, ans = INF;
for (int i=1;i<=m;i++) {
pc[i] = dis[pu[i]]+dis[pv[i]]-2*dis[lca[i] = LCA(pu[i], pv[i])];
}
r++;
while (l<r) {
int mid = (l+r)>>1;
if (check(mid)) {
ans = mid;
r = mid;
} else l = mid + 1;
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &m)==2) init(), solve();
return 0;
}
------ 本文结束 ------