QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#187743 | #5418. Color the Tree | SoyTony | RE | 2ms | 11936kb | C++14 | 4.5kb | 2023-09-24 21:37:26 | 2023-09-24 21:37:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(x=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
int t;
int n;
int a[maxn];
int stmn[maxn][18];
inline void build(){
for(int i=0;i<n;++i) stmn[i][0]=a[i];
for(int k=1;k<=17;++k){
for(int i=0;i+(1<<k)-1<n;++i){
stmn[i][k]=min(stmn[i][k-1],stmn[i+(1<<k-1)][k-1]);
}
}
}
inline int query(int l,int r){
int k=__lg(r-l+1);
return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int dep[maxn],mxdep[maxn],son[maxn];
ll buf1[maxn<<1],*p1;
int buf2[maxn<<2],*p2;
ll *f[maxn];
int *L[maxn],*R[maxn];
void dfs1(int u,int fa,int d){
dep[u]=d,mxdep[u]=d;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa) continue;
dfs1(v,u,d+1);
if(mxdep[v]>mxdep[u]) son[u]=v,mxdep[u]=mxdep[v];
}
}
void dfs2(int u,int fa){
if(u==1){
f[u]=p1,p1+=mxdep[u]-dep[u]+1;
L[u]=p2,p2+=mxdep[u]-dep[u]+1;
R[u]=p2,p2+=mxdep[u]-dep[u]+1;
for(int d=0;d<=mxdep[u]-dep[u];++d) f[u][d]=0,L[u][d]=-1,R[u][d]=-1;
}
if(!son[u]) return;
f[son[u]]=f[u]+1,L[son[u]]=L[u]+1,R[son[u]]=R[u]+1;
dfs2(son[u],u);
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa||v==son[u]) continue;
f[v]=p1,p1+=mxdep[v]-dep[v]+1;
L[v]=p2,p2+=mxdep[v]-dep[v]+1;
R[v]=p2,p2+=mxdep[v]-dep[v]+1;
for(int d=0;d<=mxdep[v]-dep[v];++d) f[v][d]=0,L[v][d]=-1,R[v][d]=-1;
dfs2(v,u);
}
}
void dfs3(int u,int fa){
f[u][0]=a[0];
if(!son[u]){
L[u][0]=R[u][0]=dep[u];
// cerr<<"u:"<<u<<endl;
// for(int d=0;d<=mxdep[u]-dep[u];++d){
// cerr<<"d:"<<d<<" f:"<<f[u][d]<<" L:"<<L[u][d]<<" R:"<<R[u][d]<<endl;
// }
return;
}
dfs3(son[u],u);
int mx=0;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa||v==son[u]) continue;
dfs3(v,u);
mx=max(mx,mxdep[v]-dep[v]);
}
for(int d=0;d<=mx;++d){
if(d+1<=mxdep[son[u]]-dep[son[u]]){
if(L[son[u]][d+1]==-1) L[son[u]][d+1]=L[son[u]][d],R[son[u]][d+1]=R[son[u]][d];
else L[son[u]][d+1]=L[son[u]][d];
}
// cerr<<"u:"<<u<<" son:"<<son[u]<<" ["<<dep[son[u]]+d-R[son[u]][d]<<","<<dep[son[u]]+d-L[son[u]][d]<<"]"<<endl;
f[son[u]][d]=min(f[son[u]][d],(ll)query(dep[son[u]]+d-R[son[u]][d],dep[son[u]]+d-L[son[u]][d]));
L[son[u]][d]=R[son[u]][d]=-1;
}
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa||v==son[u]) continue;
for(int d=0;d<=mxdep[v]-dep[v];++d){
if(d+1<=mxdep[v]-dep[v]){
if(L[v][d+1]==-1) L[v][d+1]=L[v][d],R[v][d+1]=R[v][d];
else L[v][d+1]=L[v][d];
}
// cerr<<"u:"<<u<<" v:"<<son[u]<<" ["<<dep[v]+d-R[v][d]<<","<<dep[v]+d-L[v][d]<<"]"<<endl;
f[v][d]=min(f[v][d],(ll)query(dep[v]+d-R[v][d],dep[v]+d-L[v][d]));
L[v][d]=R[v][d]=-1;
f[u][d+1]+=f[v][d];
}
}
L[u][0]=R[u][0]=dep[u];
// cerr<<"u:"<<u<<endl;
// for(int d=0;d<=mxdep[u]-dep[u];++d){
// cerr<<"d:"<<d<<" f:"<<f[u][d]<<" L:"<<L[u][d]<<" R:"<<R[u][d]<<endl;
// }
}
ll ans;
int main(){
// freopen("e.in","r",stdin);
t=read();
while(t--){
n=read();
for(int i=0;i<n;++i) a[i]=read();
build();
cnt=0;
for(int i=1;i<=n;++i) head[i]=0;
for(int i=1,u,v;i<n;++i){
u=read(),v=read();
add_edge(u,v);
}
p1=buf1,p2=buf2;
dfs1(1,0,0);
// for(int u=1;u<=n;++u) cerr<<"u:"<<u<<" son:"<<son[u]<<endl;
dfs2(1,0);
dfs3(1,0);
ans=0;
for(int d=0;d<=mxdep[1];++d){
if(d+1<=mxdep[1]){
if(L[1][d+1]==-1) L[1][d+1]=L[1][d],R[1][d+1]=R[1][d];
else L[1][d+1]=L[1][d];
}
f[1][d]=min(f[1][d],(ll)query(dep[1]+d-R[1][d],dep[1]+d-L[1][d]));
ans+=f[1][d];
}
printf("%lld\n",ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11936kb
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
Runtime Error
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...