疫情控制

题目

H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。

输入输出格式

输入格式:

第一行一个整数 n,表示城市个数。

接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从

城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。

接下来一行一个整数 m,表示军队个数。

接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎

的城市的编号。

输出格式:

共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

输入输出样例

输入样例

4

1 2 1

1 3 2

3 4 3

2

2 2

输出样例

3

思路

枚举最终答案ANS

对于在ANS时间内可以到达根节点的点记录下来

而对于不能到达的点让他尽量往根节点走

在判断那些点需要被控制 让可以到达根节点的点去控制这些点

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 50005
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
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;
}
int n, m, num[N], f[N], fa[N], d[N], temp1[N], child[N];
int tot, h[N], Next[N << 1], to[N << 1], value[N << 1];
int flag[N], temp2[N], temp3[N];
inline void add(int u, int v, int w)
{
tot ++; Next[tot] = h[u]; to[tot] = v; value[tot] = w; h[u] = tot;
}
void dfs(int u, int F, int FF, int deep)
{
flag[u] = 1;
f[u] = F; fa[u] = FF; d[u] = deep;
for (int i=h[u]; i; i=Next[i])
{
int v = to[i];
if (!flag[v]) child[u] ++, dfs(v, u, FF ? FF : v, deep + value[i]);
}
}
inline bool comp(int x, int y) {return d[x] > d[y];}
inline bool comp1(int x, int y) {return value[x] > value[y];}
inline void up(int u, int ANS)
{
int k = u;
while(ANS >= d[u] - d[k] && !flag[k]) flag[k] = 1, temp1[k] = 0, k = f[k];
if (flag[k]) return ;
temp1[k] --;
while(temp1[k] == 0 && !flag[k]) flag[k] = 1, k = f[k], temp1[k] --;
}
inline int work()
{
int L, R; L = R = 0;
in(n);
for (int i=2; i<=n; i++) {int u, v, w; in(u); in(v); in(w); add(u, v, w); add(v, u, w);R += w;}
in(m);
for (int i=1; i<=m; i++) in(num[i]);
dfs(1, 0, 0, 0);
sort(num + 1, num + m + 1, comp);
L ++; R ++;
while (L < R)
{
int mid = (L + R) >> 1;int temp4 = m+1;temp2[0] = 0;
for (int i=1; i<=n; i++) temp1[i] = child[i];
memset(flag, 0, sizeof(flag));
for (int i=m; i>=1; i--) if (d[num[i]] <= mid) temp4 = i; else up(num[i], mid);
for (int i=h[1]; i; i=Next[i]) if (!flag[to[i]]) temp2[++ temp2[0]] = i;
sort (temp2 + 1, temp2 + temp2[0] + 1, comp1);
for (int i=temp4; i<=m&&temp2[0]; i++)
{
if (!flag[fa[num[i]]]) flag[fa[num[i]]] = 1;
else
{
while(flag[to[temp2[temp2[0]]]] && temp2[0]) temp2[0]--;
if (temp2[0] == 0) break;
if (mid - d[num[i]] >= value[temp2[temp2[0]]]) flag[to[temp2[temp2[0]]]] = 1;
}
}
while(flag[to[temp2[temp2[0]]]] && temp2[0]) temp2[0]--;
if (temp2[0] == 0) R = mid; else L = mid + 1;
}
printf("%d\n", L);
return 0;
}
int TAT = work();
int main() {;}