AK-dream

【题目描述】
给定一棵$n$个点的树,标记出$m$个不同的点$s_1,s_2,s_3,\cdots,s_m$,对于每个点$s_i$求出剩下的标记点中哪个离$s_i$最近,输出距离。

【输入格式】
第一行一个整数$n$。
第$2\sim n$行每行两个整数$u,w$,第$i$行表示$i$与父亲$u$之间有一条权为$w$的边。

接下来一行一个整数$m$。
接下来一行$m$个整数表示$s_1\sim s_m$。

【输出格式】
输出一行空格隔开的$m$个整数,第$i$个数代表$s_i$的答案。

【数据范围】
$2 \le m \le n \le 10^6$,$0 \le w \le 10^9$

暴力做法就很简单 什么最短路LCA之类的随便搞一搞就行
然而还是要DP

假设根节点是1,令$f[i]$表示$i$子树内的最小答案,这个答案显然是一遍dfs就能跑出来。
子树外的答案怎么推呢?

其实也挺简单 设$ans[i]$是$i$的最终答案 设$fa$是$i$的父亲
情况1 $ans[fa]$指的就是$fa$到$i$的距离 即距离$fa$最近的标记点就是$i$
此时用$fa$的次小值 $ans2[fa]$ 来更新 $ans[i]$ 即$ans[i]=min(ans[i], ans2[fa]+dis[fa][i]) \ dis[fa][i]$指$i$到$fa$边的长度

情况2 距离$fa$最近的标记点不是$i$(或者$i$根本不是标记点)
显然$ans[i]=min(ans[i], ans[fa]+dis[fa][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
#include <iostream>
#include <cstdio>
#include <cstring>
#define re register
using namespace std;
typedef long long ll;

ll read() {
ll ret = 0, flag = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') flag = -1;
ch = getchar();
}
while (isdigit(ch)) {
ret = (ret << 1) + (ret << 3) + (ch ^ '0');
ch = getchar();
}
return ret * flag;
}

ll n, m, head[2000005], pre[2000005], to[2000005], val[2000005], sz, s[1000005];
bool spe[1000005];
ll f[1000005], ind[1000005], f2[1000005], ind2[1000005];

inline void insert(ll u, ll v, ll w) {
to[++sz] = v; pre[sz] = head[u]; head[u] = sz; val[sz] = w;
}

void update(ll x, ll y, ll v) {
if (v < f[x]) {
f2[x] = f[x]; ind2[x] = ind[x];
f[x] = v; ind[x] = y;
} else if (v < f2[x]) {
f2[x] = v; ind2[x] = y;
}
}

void dfs(ll x, ll fa) {
if (spe[x]) {
f[x] = 0;
ind[x] = x;
}
for (re int i = head[x]; i; i = pre[i]) {
ll y = to[i];
if (y == fa) continue;
dfs(y, x);
update(x, y, f[y] + val[i]);
}
}

void dfs2(ll x, ll fa) {
for (re int i = head[x]; i; i = pre[i]) {
ll y = to[i];
if (y == fa) continue;
if (y == ind[x]) {
if (f[y] > f2[x] + val[i]) {
f2[y] = f[y]; ind2[y] = ind[y];
f[y] = f2[x] + val[i]; ind[y] = ind2[x];
} else if (f2[y] > f2[x] + val[i]) {
f2[y] = f2[x] + val[i]; ind2[y] = ind2[x];
}
} else {
if (f[y] > f[x] + val[i]) {
f2[y] = f[y]; ind2[y] = ind[y];
f[y] = f[x] + val[i]; ind[y] = ind[x];
} else if (f2[y] > f[x] + val[i]) {
f2[y] = f[x] + val[i]; ind2[y] = ind[x];
}
}
dfs2(y, x);
}
}

int main() {
n = read();
for (re int i = 2; i <= n; i++) {
ll u, w;
u = read(); w = read();
insert(i, u, w); insert(u, i, w);
}
m = read();
for (re int i = 1; i <= m; i++) {
s[i] = read();
spe[s[i]] = 1;
}
for (re int i = 1; i <= n; i++) {
f[i] = f2[i] = 0x7ffffffffffffff;
}
dfs(1, 0);
dfs2(1, 0);
for (re int i = 1; i <= m; i++) {
printf("%lld ", f2[s[i]]);
}
puts("");
return 0;
}

ps: 这题$10^6$蜃臭还是要卡卡常才能过

**三年OI一场空 不开long long 见祖宗**

 评论