P6419-[COCI2014-2015#1] Kamp
题目:
题目描述:
一颗树 $n$ 个点，$n-1$ 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。
有 $K$ 个人（分布在 $K$ 个不同的点）要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发，把这 $K$ 个人分别送回去。
请你回答，对于 $i=1 \sim n$ ，如果在第 $i$ 个点举行聚会，司机最少需要多少时间把 $K$ 个人都送回家。
输入格式:
第一行两个整数 $n, K$ 。
接下来 $n-1$ 行，每行三个数 $x, y, z$ 表示 $x$ 到 $y$ 之间有一条需要花费 $z$ 时间的边。
接下来 $K$ 行，每行一个数，表示 $K$ 个人的分布。
输出格式:
输出 $n$ 个数。
第 $i$ 行的数表示：如果在第 $i$ 个点举行聚会，司机需要的最少时间。
样例:
样例输入 1:
1
2
3
4
5
6
7
8
9
| 7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7
|
样例输出 1:
1
2
3
4
5
6
7
| 11
15
10
13
16
15
10
|
样例输入 2:
1
2
3
4
5
6
7
| 5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5
|
样例输出 2:
思路:
实现:
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
| #include "ybwhead/ios.h"
#define int long long
int n, k;
const int maxn = 5e5 + 10;
struct Edge_node
{
int v, w, nxt;
} e[maxn << 1];
int head[maxn], tot;
void __ADD(int u, int v, int w)
{
e[++tot] = (Edge_node{v, w, head[u]});
head[u] = tot;
}
void add(int u, int v, int w)
{
__ADD(u, v, w);
__ADD(v, u, w);
}
int c[maxn], sz[maxn], dp[maxn], len[maxn], len1[maxn], id[maxn];
void dp1(int u, int f)
{
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == f)
continue;
dp1(v, u);
if (sz[v])
{
sz[u] += sz[v];
dp[u] += dp[v] + 2 * e[i].w;
int now = len[v] + e[i].w;
if (now >= len[u])
{
len1[u] = len[u];
len[u] = now;
id[u] = v;
}
else
{
len1[u] = max(len1[u], now);
}
}
}
}
int f[maxn];
void dp2(int u, int fa)
{
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)
continue;
if (!sz[v])
f[v] = f[u] + 2 * e[i].w, len[v] = len[u] + e[i].w;
else if (k - sz[v])
{
f[v] = f[u];
if (id[u] != v && len[v] < len[u] + e[i].w)
len1[v] = len[v], len[v] = len[u] + e[i].w, id[v] = u;
else if (len[v] < len1[u] + e[i].w)
len1[v] = len[v], len[v] = len1[u] + e[i].w, id[v] = 1;
else if (len1[v] < len[u] + e[i].w && id[u] != v)
len1[v] = len[u] + e[i].w;
else if (len1[v] < len1[u] + e[i].w)
len1[v] = len1[u] + e[i].w;
}
else
f[v] = dp[v];
dp2(v, u);
}
}
signed main()
{
yin >> n >> k;
for (int i = 1; i < n; i++)
{
int x, y, z;
yin >> x >> y >> z;
add(x, y, z);
}
for (int i = 1; i <= k; i++)
yin >> c[i], sz[c[i]]++;
dp1(1, 0);
f[1] = dp[1];
dp2(1, 0);
for (int i = 1; i <= n; i++)
yout << f[i] - len[i] << endl;
return 0;
}
|