QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109019#5418. Color the TreewhyWA 20ms5276kbC++172.7kb2023-05-27 09:36:362023-05-27 09:36:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-27 09:36:37]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:5276kb
  • [2023-05-27 09:36:36]
  • 提交

answer

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+86;
const ll INF=0x3f3f3f3f3f3f3f3f;

int T,n;
ll a[N],b[N];
struct edge{int to,nxt;}e[N<<1];
int head[N],tot;
void add(int u,int v){e[++tot]={v,head[u]},head[u]=tot;}

struct node{int hson,dep,mdep;}p[N];
void dfs1(int u,int fa)
{
    p[u].hson=0;
    p[u].dep=p[fa].dep+1;
    p[u].mdep=p[u].dep;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs1(v,u);
        p[u].mdep=max(p[u].mdep,p[v].mdep);
        if(!p[u].hson||p[p[u].hson].mdep<p[v].mdep) p[u].hson=v;
    }
}

ll Min[N][21],log_2[N];
ll query(int l,int r)
{
    l++,r++;
	int k=log_2[r-l+1];
	return min(Min[l][k],Min[r-(1<<k)+1][k]);
}
void init()
{
	for(int i=2;i<=n;i++)
		log_2[i]=log_2[i-1]+((i&(i-1))?0:1);
	for(int j=1;j<=log_2[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
}

ll f[N][50],cnt=1;
void dfs2(int u,int fa,int top)
{//printf("%d\n",u);
    if(p[u].hson) dfs2(p[u].hson,u,top);
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa||v==p[u].hson) continue;
        cnt++;
        for(int j=0;j<=p[v].mdep-p[v].dep;j++)
            f[cnt][j]=0;
        // memset(f[cnt],0,(p[v].mdep-p[v].dep+1)<<3);
        dfs2(v,u,v);
        for(int j=0;j<=p[v].mdep-p[v].dep;j++)
            f[cnt-1][p[v].dep-p[top].dep+j]=min(query(p[v].dep-p[u].dep+j,p[v].dep-p[top].dep+j),f[cnt-1][p[v].dep-p[top].dep+j]+f[cnt][j]);//printf("%d %d %lld %lld\n",u,p[v].dep-p[top].dep+j,query(p[v].dep-p[u].dep+j,p[v].dep-p[top].dep+j),f[cnt-1][p[v].dep-p[top].dep+j]);
        cnt--;
    }
    f[cnt][p[u].dep-p[top].dep]=query(0,p[u].dep-p[top].dep);//printf("U: %d %lld %d %lld\n",u,f[1][0],p[u].dep-p[top].dep,query(0,p[u].dep-p[top].dep));
}

template<typename T>
inline void read(T &x)
{
    T k=1;char ch=getchar();x=0;
    while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=k;
}

signed main()
{
    read(T);
    while(T--)
    {
        read(n);
        memset(head+1,0,n<<2);
        tot=0;
        cnt=1;
        for(int i=0;i<=n-1;i++)
            read(Min[i+1][0]),a[i]=Min[i+1][0];
        init();
        for(int i=1,u,v;i<=n-1;i++)
            read(u),read(v),add(u,v),add(v,u);
        dfs1(1,0);
        dfs2(1,0,1);
        ll sum=0;
        for(int i=0;i<=p[1].mdep-1;i++)
            sum+=f[1][i];//printf("%d %lld\n",i,f[1][i]);
        printf("%lld\n",sum);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 1756kb

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: 6ms
memory: 1496kb

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: 16ms
memory: 1676kb

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: 0
Accepted
time: 17ms
memory: 3508kb

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:

427
520
443
359
427
408
371
415
482
436
269
530
478
485
435
453
418
503
443
453
405
425
347
564
297
435
559
453
213
395

result:

ok 30 numbers

Test #5:

score: 0
Accepted
time: 12ms
memory: 1488kb

input:

3000
74
555233197 518812085 998593787 821753058 967306600 663279435 696954042 885219300 489323226 146136486 447383587 785317885 838306349 708275482 715157265 298848995 400280904 374077023 673881523 207667786 885945020 459791675 992519779 327830583 821713695 253985403 926395863 419409783 138881726 80...

output:

6742611216
5794349776
3087356867
4707144715
2761702533
3246645261
4802134565
2999820393
4887036613
2784978973
3593730307
4783057633
4621084176
4331196830
4242984461
2287799528
3027767371
3699192818
3888960419
6398323452
2766114996
1734720583
6543430036
1955540148
5464479116
3177069662
5145942113
302...

result:

ok 3000 numbers

Test #6:

score: 0
Accepted
time: 12ms
memory: 1740kb

input:

300
621
259262308 372414267 976777900 567821544 262206094 972740633 932600104 702535786 494092920 919901107 797100568 708295156 632473907 101958470 952065075 970482879 183543308 323078517 719011818 352232578 159576652 124505381 125133768 492132730 331846050 577415810 369370004 871034176 529186574 44...

output:

8143086197
8197999468
5370721620
5343127707
5868323006
7992625789
5749423188
5019336842
5319894438
5228239187
5391752908
6084605805
6792215852
6057910407
8471127525
2719747215
6909535671
5100581420
5878004843
5586237425
6343902433
9390109727
5651124389
5472179570
7945151774
5064107530
4433748186
571...

result:

ok 300 numbers

Test #7:

score: 0
Accepted
time: 20ms
memory: 3356kb

input:

30
5308
560111855 290003681 946208440 140658046 860834453 480249720 506770353 922783074 600720525 693059141 436061359 545671168 528534807 339705109 831632761 570564203 113225613 578123930 293066534 269996029 765346927 443717770 933144287 856263710 475170893 174188152 464281143 864607591 443380284 12...

output:

8829755982
7996435040
9259425768
7684533044
9842457103
3917213508
5939555066
8695995697
9431906955
7466353560
8322921019
8970732656
8099619221
9390765699
6773331885
8521621715
9998520099
7876760589
6482847050
10167157889
8563826262
5569616375
7783052317
7313404561
7224267995
8986870714
9082031438
99...

result:

ok 30 numbers

Test #8:

score: -100
Wrong Answer
time: 11ms
memory: 5276kb

input:

30
235
99 26 36 76 38 12 81 57 32 53 24 100 83 36 73 40 99 67 25 59 13 53 26 96 88 91 70 75 50 28 43 91 28 80 21 10 28 96 81 46 93 48 47 65 16 51 39 13 17 68 87 47 11 53 35 59 95 17 12 28 42 72 69 93 10 99 55 36 17 10 17 82 46 47 30 13 33 46 47 82 26 70 89 11 84 15 75 82 23 15 26 21 33 100 80 68 59 ...

output:

733
979
713
711
676
776
791
938
1002
922
1314
672
1059
944
994
1482
746
954
829
825
799
545
884
1057
969
882
778
1186
767
906

result:

wrong answer 1st numbers differ - expected: '1853', found: '733'