QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107661#5418. Color the Treegtm1514WA 33ms3672kbC++142.9kb2023-05-22 11:59:072023-05-22 11:59:08

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-22 11:59:08]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:3672kb
  • [2023-05-22 11:59:07]
  • 提交

answer

/*你说的对,但是大样例呢*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#define int long long
using namespace std;
int n,a[100010];
struct ST{
    int st[100010][21];
    void build(){
        for(int i=0;i<n;i++)st[i][0]=a[i];
        for(int j=1;j<__lg(n);j++){
            for(int i=0;i+(1<<j)-1<n;i++){
                st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
            }
        }
    }
    int query(int l,int r){
        int k=__lg(r-l+1);
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
}st;
struct node{
    int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
    edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int dep[100010],son[100010],sec[100010];
void dfs1(int x,int f){
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f){
            dfs1(edge[i].v,x);
            if(dep[son[x]]<dep[edge[i].v])sec[x]=dep[son[x]],son[x]=edge[i].v;
            else if(sec[x]<dep[edge[i].v])sec[x]=dep[edge[i].v];
        }
    }
    sec[x]++;
    dep[x]=dep[son[x]]+1;
}
int buf1[100010],*dp[100010],*now1=buf1;
int buf2[100010],*lz[100010],*now2=buf2;
void dfs2(int x,int f){
    if(son[x]){
        dp[son[x]]=dp[x]+1;lz[son[x]]=lz[x]+1;
        dfs2(son[x],x);
    }
    dp[x][0]=a[0];
    for(int i=1;i<sec[x];i++)dp[x][i]=min(dp[x][i],st.query(lz[x][i]-1,i-1));
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f&&edge[i].v!=son[x]){
            dp[edge[i].v]=now1;now1+=dep[edge[i].v];
            lz[edge[i].v]=now2;now2+=dep[edge[i].v];
            dfs2(edge[i].v,x);
            for(int j=1;j<=dep[edge[i].v];j++){
                dp[edge[i].v][j-1]=min(dp[edge[i].v][j-1],st.query(lz[edge[i].v][j-1]-1,j-1));
                dp[x][j]+=dp[edge[i].v][j-1];
            }
        }
    }
    for(int i=0;i<sec[x];i++)dp[x][i]=min(dp[x][i],a[i]);
    for(int i=0;i<sec[x];i++)lz[x][i]=i+1;
}
void clear(){
    t=0;
    for(int i=0;i<=n;i++)head[i]=son[i]=dep[i]=sec[i]=buf1[i]=buf2[i]=0;
    for(int i=0;i<=__lg(n);i++)for(int j=0;j<n;j++)st.st[j][i]=0;
    now1=buf1;now2=buf2;
}
signed main(){
    // freopen("color.in","r",stdin);
    // freopen("color.out","w",stdout);
    int tim=1;
    scanf("%lld",&tim);
    while(tim--){
        scanf("%lld",&n);
        for(int i=0;i<n;i++)scanf("%lld",&a[i]);
        st.build();
        for(int i=1;i<n;i++){
            int u,v;scanf("%lld%lld",&u,&v);
            add(u,v);add(v,u);
        }
        dfs1(1,0);
        dp[1]=now1;now1+=dep[1];lz[1]=now2;now2+=dep[1];
        dfs2(1,0);
        int ans=0;
        for(int i=0;i<sec[1];i++)ans+=dp[1][i];
        for(int i=sec[1];i<dep[1];i++){
            dp[1][i]=min(dp[1][i],st.query(lz[1][i],i));
            ans+=dp[1][i];
        }
        printf("%lld\n",ans);
        clear();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3588kb

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: -100
Wrong Answer
time: 33ms
memory: 3672kb

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
43
140
189
170
173
137
233
94
163
273
80
350
156
133
146
159
240
269
137
222...

result:

wrong answer 59th numbers differ - expected: '53', found: '43'