QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110328#5418. Color the TreeE_huanRE 47ms15252kbC++141.5kb2023-06-01 15:57:412023-06-01 15:57:42

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-01 15:57:42]
  • 评测
  • 测评结果:RE
  • 用时:47ms
  • 内存:15252kb
  • [2023-06-01 15:57:41]
  • 提交

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...

output:


result: