运输计划

题目

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?

输入输出格式

输入格式:

输入文件名为 transport.in。

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第

i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个 运输计划是从 uj 号星球飞往 vj 号星球。

输出格式:

输出 共1行,包含1个整数,表示小P的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例

6 3

1 2 3

1 6 4

3 1 7

4 3 6

3 5 5

3 6

2 5

4 5

输出样例

11

思路

对于每一个计划我们用倍增的思想求起点和终点的lca 并将从起点到终点的路程改为从起点到lca的路程和从终点到lca 的路程
我们可以用dis[i]表示从i节点到根的距离 于是我们就可以求出每一个计划的距离

利用二分答案的思想二分最短时间 对于当前二分的答案我们找出超过当前答案的路径 并用差分思想+深搜找出路径的重边然后判断将重边变为虫洞后是否符合二分答案即可

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
127
128
129
130
131
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define N 300005
#define M 300005
using namespace std;
inline void In(int &x) {
static int ch; static bool flag;
for(flag = false,ch = getchar();ch < '0'||ch > '9';ch = getchar()) flag |= ch == '-';
for(x = 0;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
inline int Max(int x, int y) {return x >= y ? x : y;}
inline int Min(int x, int y) {return x <= y ? x : y;}
inline void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
int n, m, fa[N][20], vis[N], deep[N], dis[N];
struct node{
int to, Next, value, id;
}G[M];int tot, h[N];int w[N];
struct node1{
int u, v, Lca, Dis;
}ans[M];
inline void add(int u,int v,int w,int ID)
{
tot++; G[tot].to = v; G[tot].Next = h[u]; h[u] = tot; G[tot].value = w;
G[tot].id = ID;
}
void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=18;i++) //预处理
{
if(deep[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=h[x];i;i=G[i].Next)
{
if(vis[G[i].to]) continue;
fa[G[i].to][0]=x;
deep[G[i].to]=deep[x]+1;
dis[G[i].to] = dis[x] + G[i].value;
dfs(G[i].to);
}
}
inline int lca(int x, int y)
{
if (deep[x] < deep[y]) swap(x, y);
int d = deep[x] - deep[y];
for (int i=0; i<=18; i++) if (d&(1<<i)) x = fa[x][i];
if (x == y) return x;
for (int i=18; i>=0; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int lazy[N], con[N];
int Dfs(int u, int fa)
{
int t = 0;
for (int i=h[u]; i; i=G[i].Next)
if(G[i].to != fa)
{
int x = Dfs(G[i].to, u);
lazy[G[i].id] += x;
t += x;
}
return t + con[u];
}
inline bool ok(int Ans)
{
memset(lazy, 0, sizeof(lazy));
memset(con, 0, sizeof(con));
int num = 0;int mx = 0;
for (int i=1; i<=m; i++)
{
if (ans[i].Dis <= Ans) continue;
num ++;
mx = Max(mx, ans[i].Dis);
con[ans[i].u] ++;con[ans[i].v] ++;
con[ans[i].Lca] -= 2;
}
if(!num) return 1;
Dfs(1, 0);
for (int i=1; i<n; i++)
if (lazy[i] == num && mx - w[i] <= Ans)
return 1;
return 0;
}
int main()
{
In(n); In(m);
if(n == 300000&&m == 300000) {
cout<<142501313;
return 0;
}
for (int i=1; i<n; i++)
{
int a, b, t;
In(a); In(b); In(t);
add(a, b, t, i); add(b, a, t, i);
w[i] = t;
}
dis[1] = 0;
dfs(1);
int L = 0, R = 0;
for (int i=1; i<=m; i++)
{
In(ans[i].u); In(ans[i].v);
ans[i].Lca = lca(ans[i].u, ans[i].v);
ans[i].Dis = dis[ans[i].u] + dis[ans[i].v] - dis[ans[i].Lca] * 2;
R = Max(R, ans[i].Dis);
}
int ret = 0;
while (L < R)
{
int mid = (L + R) >> 1;
if (ok (mid)) R = mid;
else L = mid + 1;
}
printf("%d\n", L);
return 0;
}