QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187748#5418. Color the TreeSoyTonyRE 2ms12032kbC++144.6kb2023-09-24 21:39:352023-09-24 21:39:35

Judging History

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

  • [2023-09-24 21:39:35]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:12032kb
  • [2023-09-24 21:39:35]
  • 提交

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(L[son[u]][d]!=-1&&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;
        if(L[son[u]][d]!=-1) 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(L[v][d]!=-1&&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;
            if(L[v][d]!=-1) 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(L[1][d]!=-1&&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];
            }
            if(L[1][d]!=-1) 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: 12032kb

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...

output:


result: