QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129534 | #5418. Color the Tree | lhzawa | WA | 29ms | 13520kb | C++14 | 2.7kb | 2023-07-22 20:26:02 | 2023-07-22 20:26:05 |
Judging History
answer
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: E. Color the Tree
// Contest: Codeforces - The 2022 ICPC Asia Nanjing Regional Contest
// URL: https://codeforces.com/gym/104128/problem/E
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 18;
vector<int> G[N], D[N];
int f[N][M];
int dep[N];
void dfs_dep(int u) {
for (int i = 1; i < M; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
D[dep[u]].push_back(u);
for (int v : G[u]) {
if (v == f[u][0]) {
continue;
}
f[v][0] = u, dep[v] = dep[u] + 1, dfs_dep(v);
}
return ;
}
int LCA(int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
for (int i = 0, dc = dep[u] - dep[v]; i < M; i++) {
if ((dc >> i) & 1) {
u = f[u][i];
}
}
if (u == v) {
return u;
}
for (int i = M - 1; ~ i; i--) {
if (f[u][i] != f[v][i]) {
u = f[u][i], v = f[v][i];
}
}
return f[u][0];
}
vector<int> vG[N];
long long mn[N][M];
long long query(int l, int r) {
int k = __lg(r - l + 1);
return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
long long dfs_f(int u, int fa, int d) {
long long res = LLONG_MAX;
if (dep[u] == d);
else {
res = 0;
for (int v : vG[u]) {
res += dfs_f(v, u, d);
}
}
return min(res, query(d - dep[u], d - (dep[fa] + 1)));
}
int stk[N], top;
long long calc(int d) {
top = stk[1] = 1, vG[1].clear();
for (int u : D[d]) {
vG[u].clear();
int l = LCA(u, stk[top]);
if (l == stk[top]) {
stk[++top] = u;
continue;
}
for (; dep[l] < dep[stk[top - 1]]; top--) {
vG[stk[top - 1]].push_back(stk[top]);
}
if (l == stk[top - 1]) {
vG[l].push_back(stk[top]), top--;
}
else {
vG[l].clear(), vG[l].push_back(stk[top]), stk[top] = l;
}
stk[++top] = u;
}
for (; top > 1; top--) {
vG[stk[top - 1]].push_back(stk[top]);
}
return dfs_f(1, 0, d);
}
void solve() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &mn[0][i]);
}
for (int i = 1; (1 << i) <= n; i++) {
for (int l = 0, r = (1 << i) - 1; r < n; l++, r++) {
mn[i][l] = min(mn[i - 1][l], mn[i - 1][l + (1 << (i - 1))]);
}
}
for (int i = 1; i <= n; i++) {
G[i].clear();
}
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y), G[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
D[i].clear();
}
dep[1] = 1;
dfs_dep(1);
long long ans = mn[0][0];
for (int i = 2; i <= n && ! D[i].empty(); i++) {
ans += calc(i);
}
printf("%lld\n", ans);
return ;
}
int main() {
int _;
scanf("%d", &_);
for (; _; _--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 13520kb
input:
3 4 10 15 40 1 1 2 2 3 2 4 5 10 5 1 100 1000 1 2 2 3 2 4 4 5 4 1000 200 10 8 1 2 2 3 3 4
output:
35 17 1218
result:
ok 3 number(s): "35 17 1218"
Test #2:
score: 0
Accepted
time: 29ms
memory: 12732kb
input:
3000 54 43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44 1 2 1 3 2 4 3 5 4 6 2 7 4 8 1 9 3 10 1 11 8 12 2 13 9 14 1 15 1 16 15 17 15 18 7 19 1 20 19 21 13 22 10 23 17 24 9 25 9 26 24 27 8 28...
output:
180 168 222 230 156 240 225 126 100 81 155 73 154 127 149 124 228 230 132 187 153 170 78 282 195 286 191 211 119 197 211 233 88 252 239 233 173 180 195 121 109 148 180 175 226 210 182 97 199 59 56 31 115 204 203 172 139 208 53 140 189 170 173 137 233 94 163 273 80 350 156 133 146 159 240 269 137 222...
result:
ok 3000 numbers
Test #3:
score: -100
Wrong Answer
time: 29ms
memory: 13328kb
input:
300 474 5 24 21 41 15 23 43 48 32 19 27 40 10 49 40 6 18 41 43 31 45 18 35 36 12 10 23 45 28 23 14 43 37 45 12 16 20 17 49 13 22 8 30 19 27 40 22 14 30 47 16 39 25 48 21 26 50 8 14 26 9 30 41 15 44 24 16 46 50 39 25 47 24 45 21 18 26 21 5 39 15 10 47 48 11 44 44 33 23 14 35 39 35 30 38 9 13 15 39 5 ...
output:
329 183 264 219 323 220 348 342 410 395 80 201 299 144 207 408 360 215 283 104 320 394 277 210 273 285 242 253 265 379 360 322 202 351 195 196 266 270 171 342 239 283 286 300 331 317 345 268 173 296 275 224 480 330 264 162 199 378 254 214 231 293 229 259 241 268 380 419 233 185 364 341 328 237 320 3...
result:
wrong answer 150th numbers differ - expected: '446', found: '464'