QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#148669#5418. Color the Tree11d10xyWA 35ms9628kbC++141.4kb2023-08-23 17:21:362023-08-23 20:25:24

Judging History

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

  • [2023-08-23 20:25:24]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:9628kb
  • [2023-08-23 17:21:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int>G[100010];
int n,mi[100010][25],mxdis[100010],dfn[100010],las[100010],tot;
ll f[100010];
auto query=[](int l,int r){int g=__lg(r-l+1);return min(mi[l][g],mi[r-(1<<g)+1][g]);};
void dfs(int u,int fa){
    if(fa)G[u].erase(find(begin(G[u]),end(G[u]),fa));
    for(int&v:G[u]){
        dfs(v,u);
        if(mxdis[v]+1>mxdis[u])
         mxdis[u]=mxdis[v]+1,swap(v,G[u][0]);
    }
}
auto upd=[](int ind,int now){if(las[ind]<=now)f[ind]=min(f[ind],(ll)query(las[ind],now)),las[ind]=now+1;return f[ind];};
void solve(int u){
    dfn[u]=++tot;
    for(int v:G[u]){
        solve(v);
        if(v!=G[u][0])
        for(int i=0;i<=mxdis[v];i++){
            upd(dfn[u]+i+1,i);
            f[dfn[u]+i+1]+=upd(dfn[v]+i,i);
        }
    }
}
int main(){
    int T;for(cin>>T;T--;){
        cin>>n;
        for(int i=1;i<=n;i++)dfn[i]=mxdis[i]=las[i]=0,f[i]=1e18,G[i].clear();
        for(int i=0;i<n;i++)scanf("%d",&mi[i][0]);
        for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
        for(int i=1;i<=20;i++)
        for(int j=0;j+(1<<i)<=n;j++)
        mi[j][i]=min(mi[j][i-1],mi[j+(1<<i-1)][i-1]);
        dfs(1,0),solve(1);
        ll ans=0;
        for(int i=0;i<=mxdis[1];i++)ans+=upd(i+1,i);
        cout<<ans<<endl;
    }
    return 0;
}

詳細信息

Test #1:

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

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: 35ms
memory: 9628kb

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
92
131
179
127
221
205
104
100
79
139
68
129
91
142
79
153
176
104
127
111
90
75
173
174
90
116
154
30
87
54
152
63
240
197
143
150
169
121
112
78
72
165
123
217
144
122
73
81
59
56
22
115
131
165
63
95
163
50
95
94
88
159
119
190
58
151
199
80
294
142
56
82
144
197
207
72
121
65
192
84
62
99
91...

result:

wrong answer 2nd numbers differ - expected: '168', found: '92'