QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446871#8518. Roars III2745518585WA 17ms106864kbC++203.5kb2024-06-17 17:06:072024-06-17 17:06:07

Judging History

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

  • [2024-06-17 17:06:07]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:106864kb
  • [2024-06-17 17:06:07]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1000001;
int n,tot;
ll f[N],g[N],e[N];
char b[N];
vector<int> a[N];
struct tree
{
    int b,bm;
}T[N];
struct str
{
    int x,w;
    str():x(0),w(-1e9) {}
    str(int x,int w):x(x),w(w) {}
}h1[N],h2[N];
str max(str a,str b)
{
    return a.w>b.w?a:b;
}
namespace sgt
{
    struct tree
    {
        int l,r,k;
        str s;
    }T[N<<2];
    void pushup(int x)
    {
        T[x].s=max(T[x<<1].s,T[x<<1|1].s);
    }
    void pushdown(int x)
    {
        if(T[x].k==0) return;
        T[x<<1].s.w+=T[x].k;
        T[x<<1].k+=T[x].k;
        T[x<<1|1].s.w+=T[x].k;
        T[x<<1|1].k+=T[x].k;
        T[x].k=0;
    }
    void build(int x,int l,int r)
    {
        T[x].l=l,T[x].r=r;
        if(l==r) return;
        int z=l+r>>1;
        build(x<<1,l,z);
        build(x<<1|1,z+1,r);
        pushup(x);
    }
    void add1(int x,int l,int r,int k)
    {
        if(T[x].l>=l&&T[x].r<=r)
        {
            T[x].s.w+=k;
            T[x].k+=k;
            return;
        }
        pushdown(x);
        int z=T[x].l+T[x].r>>1;
        if(l<=z) add1(x<<1,l,r,k);
        if(r>z) add1(x<<1|1,l,r,k);
        pushup(x);
    }
    void add2(int x,int q,str k)
    {
        if(T[x].l==T[x].r)
        {
            T[x].s=k;
            return;
        }
        pushdown(x);
        int z=T[x].l+T[x].r>>1;
        if(q<=z) add2(x<<1,q,k);
        else add2(x<<1|1,q,k);
        pushup(x);
    }
    str sum(int x,int l,int r)
    {
        if(l>r) return str();
        if(T[x].l>=l&&T[x].r<=r) return T[x].s;
        pushdown(x);
        int z=T[x].l+T[x].r>>1;
        str s;
        if(l<=z) s=max(s,sum(x<<1,l,r));
        if(r>z) s=max(s,sum(x<<1|1,l,r));
        return s;
    }
}
void dfs1(int x,int fa)
{
    T[x].b=++tot;
    for(auto i:a[x])
    {
        if(i==fa) continue;
        dfs1(i,x);
        sgt::add2(1,T[i].b,str(i,0));
        if(b[i]=='0')
        {
            h1[i]=sgt::T[1].s;
            sgt::add2(1,T[h1[i].x].b,str());
            f[i]+=h1[i].w;
        }
        sgt::add1(1,T[i].b,T[i].bm,1);
        f[x]+=f[i];
    }
    T[x].bm=tot;
}
void dfs2(int x,int fa)
{
    e[x]=g[x];
    if(b[x]=='0'&&sgt::T[1].s.x!=0) e[x]+=sgt::T[1].s.w;
    for(auto i:a[x])
    {
        if(i==fa) continue;
        g[i]=g[x];
        sgt::add2(1,T[x].b,str(x,0));
        if(b[x]=='0')
        {
            h2[i]=max(sgt::sum(1,1,T[i].b-1),sgt::sum(1,T[i].bm+1,n));
            sgt::add2(1,T[h2[i].x].b,str());
            g[i]+=h2[i].w;
        }
        sgt::add1(1,1,n,1);
        sgt::add1(1,T[i].b,T[i].bm,-2);
        if(b[i]=='0')
        {
            sgt::add2(1,T[h1[i].x].b,h1[i]);
            g[i]-=h1[i].w;
        }
        sgt::add2(1,T[i].b,str());
        dfs2(i,x);
        sgt::add2(1,T[i].b,str(i,0));
        if(b[i]=='0') sgt::add2(1,T[h1[i].x].b,str());
        sgt::add1(1,1,n,-1);
        sgt::add1(1,T[i].b,T[i].bm,2);
        if(b[x]=='0') sgt::add2(1,T[h2[i].x].b,h2[i]);
        sgt::add2(1,T[x].b,str());
    }
}
int main()
{
    scanf("%d%s",&n,b+1);
    for(int i=1;i<=n-1;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    sgt::build(1,1,n);
    dfs1(1,0);
    g[1]=f[1];
    dfs2(1,0);
    for(int i=1;i<=n;++i)
    {
        printf("%lld ",e[i]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 105344kb

input:

5
10101
1 2
2 3
2 4
4 5

output:

2 2 2 3 3 

result:

ok 5 number(s): "2 2 2 3 3"

Test #2:

score: 0
Accepted
time: 11ms
memory: 104908kb

input:

1
0

output:

0 

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 17ms
memory: 102212kb

input:

1
1

output:

0 

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 4ms
memory: 104100kb

input:

2
10
1 2

output:

0 1 

result:

ok 2 number(s): "0 1"

Test #5:

score: 0
Accepted
time: 4ms
memory: 103868kb

input:

3
100
2 3
2 1

output:

0 1 2 

result:

ok 3 number(s): "0 1 2"

Test #6:

score: 0
Accepted
time: 3ms
memory: 106616kb

input:

4
1100
4 1
4 3
4 2

output:

1 1 3 1 

result:

ok 4 number(s): "1 1 3 1"

Test #7:

score: -100
Wrong Answer
time: 7ms
memory: 106864kb

input:

5
10100
4 5
1 3
2 1
3 5

output:

1 1 1 7 4 

result:

wrong answer 1st numbers differ - expected: '0', found: '1'