QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110328 | #5418. Color the Tree | E_huan | RE | 47ms | 15252kb | C++14 | 1.5kb | 2023-06-01 15:57:41 | 2023-06-01 15:57:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
int res=0; bool f=0;
char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) res=res*10+(ch^'0'),ch=getchar();
return f?-res:res;
}
const int N=5010,M=N<<1;
int n,a[N];
ll f[N][N];
int idx=1,e[M],ne[M],head[N];
inline void add(int x,int y) {
e[++idx]=y;
ne[idx]=head[x];
head[x]=idx;
}
ll space[N],*tmp;
// ll *f[N];
int son[N],depth[N];
void dfs(int u,int fa) {
son[u]=0;
for(int i=head[u];i;i=ne[i]) {
int v=e[i];
if(v==fa) continue;
dfs(v,u);
if(depth[v]>depth[son[u]]) son[u]=v;
}
depth[u]=depth[son[u]]+1;
}
void dp(int u,int fa) {
f[u][0]=a[0];
for(int i=head[u];i;i=ne[i]) {
int v=e[i];
if(v==fa) continue;
dp(v,u);
for(int i=1;i<=depth[v];i++) f[u][i]+=f[v][i-1];
}
for(int i=0;i<depth[u];i++) f[u][i]=min(f[u][i],1ll*a[i]);
}
int main() {
int TT=read();
while(TT--) {
n=read();
idx=1; for(int i=1;i<=n;i++) head[i]=0;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=0;
for(int i=0;i<n;i++) a[i]=read();
for(int i=1;i<n;i++) {
int a=read(),b=read();
add(a,b); add(b,a);
}
dfs(1,0);
dp(1,0);
ll ans=0;
for(int i=0;i<=depth[1];i++) ans+=f[1][i];
printf("%lld\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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: 18ms
memory: 4020kb
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: 0
Accepted
time: 47ms
memory: 15252kb
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:
ok 300 numbers
Test #4:
score: -100
Runtime Error
input:
30 4926 18 13 47 7 21 39 28 48 21 44 14 18 39 13 46 33 6 49 9 7 10 29 29 25 38 15 16 42 41 41 40 14 26 13 6 19 17 31 24 18 30 24 48 46 38 21 28 42 29 50 33 28 18 26 18 42 13 23 35 20 32 6 17 25 44 46 35 36 50 24 7 29 34 14 41 41 8 33 22 46 7 6 22 40 24 8 44 36 38 13 37 37 25 22 7 43 50 33 19 44 24 4...