QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110343 | #5418. Color the Tree | E_huan | WA | 1ms | 3600kb | C++14 | 1.7kb | 2023-06-01 16:39:06 | 2023-06-01 17:00: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=200010,M=N<<1,inf=1e9;
int n,a[N],s[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,*f[N];
int son[N],depth[N];
int d[N]; // 到根距离
void dfs(int u,int fa) {
d[u]=d[fa]+1;
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]=++tmp; f[u][0]=s[d[u]];
if(son[u]) dp(son[u],u);
for(int i=head[u];i;i=ne[i]) {
int v=e[i];
if(v==fa||v==son[u]) continue;
dp(v,u);
for(int i=0;i<depth[v];i++) {
f[u][i+1]+=f[v][i];
f[u][i+1]=min(f[u][i+1],1ll*a[i+1]);
}
}
}
int main() {
int TT=read();
while(TT--) {
n=read();
idx=1; for(int i=1;i<=n;i++) head[i]=0;
for(int i=0;i<n;i++) a[i]=read(),s[i]=min((i?s[i-1]:inf),a[i]);
for(int i=1;i<n;i++) {
int a=read(),b=read();
add(a,b); add(b,a);
}
dfs(1,0);
tmp=space;
dp(1,0);
ll ans=0;
for(int i=0;i<depth[1];i++) ans+=f[1][i];
printf("%lld\n",ans);
while(tmp!=space) (*tmp)=0,tmp--; // 清空
(*tmp)=0; // space 也要清
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3600kb
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:
22 9 219
result:
wrong answer 1st numbers differ - expected: '35', found: '22'