[Codeforces1088F] Ehab and a weird weight formula

做法

奇怪的题目...

先把点按 \(a_i\) 从小到大重新标个号。接下来我们假设 \(a_i < a_{i+1}\)

\(1\) 看作根,显然可以通过调整使每个点的父亲编号都比他小。

把两种贡献一起考虑,定义边 \(\{u, fa(u)\}\) 的贡献为 \(a_u + (\lceil\log_2{dist(u,fa(u))}\rceil+1)a_{fa(u)}\),对每个 \(u\) 去找能使代价最小的 \(fa(u)\)。由于这个树的特殊性质,点 \(u\) 最优的父亲一定是原树上 \(u\) 的祖先,所以倍增一下即可。

时间复杂度 \(\mathcal O(n \log n)\)

代码

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 500010;

typedef long long ll;

int l[maxn], e = 0;

struct Edge {
int v, x;
} E[maxn<<1];

int n, a[maxn], ind[maxn], ni[maxn], _a[maxn];
int fa[maxn][20], mn[maxn][20]; // 距离不超过 2^k 的点

int cmp(int x, int y) {
return a[x] < a[y];
}

void dfs(int u, int f) {
fa[u][0] = f; if (u != 1) mn[u][0] = a[f]; else mn[u][0] = 0x3f3f3f3f;
for (int i = 1; i < 20; i++) {
fa[u][i] = fa[fa[u][i-1]][i-1];
mn[u][i] = min(mn[u][i-1], mn[fa[u][i-1]][i-1]);
}
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f) {
dfs(v, u);
}
}
}

inline void addEdge(int u, int v) {
E[e].v = v, E[e].x = l[u], l[u] = e++;
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d", &n);
memset(mn[0], 0x3f, sizeof(mn[0]));
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ind[i] = i;
sort(ind+1, ind+n+1, cmp);
for (int i = 1; i <= n; i++) _a[i] = a[ind[i]], ni[ind[i]] = i;
for (int i = 1; i <= n; i++) a[i] = _a[i];
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
u = ni[u], v = ni[v];
addEdge(u, v), addEdge(v, u);
}
dfs(1, 0);
ll ans = 0;
for (int i = 2; i <= n; i++) {
ll res = 1e18;
for (int j = 0; j < 20; j++) {
res = min(res, 1LL * (j + 1) * mn[i][j]);
}
ans += res + a[i];
}
printf("%lld\n", ans);
return 0;
}