QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#668390#7305. Lowest Common AncestorAfterlife#RE 3ms13820kbC++202.8kb2024-10-23 14:12:012024-10-23 14:12:01

Judging History

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

  • [2024-10-23 14:12:01]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:13820kb
  • [2024-10-23 14:12:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+1e3+7;

int n,w[N];

vector<int> g[N];

int dep[N],top[N],fa[N],ord[N],st[N],ed[N],sz[N],son[N],dc;

void dfs1(int x)
{
    sz[x]=1;
    for(auto v:g[x])
    {
        if(v==fa[x])
            continue;
        fa[v]=x;
        dep[v]=dep[x]+1;
        dfs1(v);
        w[v]-=w[x];
        sz[x]+=sz[v];
        if(sz[v]>sz[son[x]])
            son[x]=v;
    }
}

void dfs2(int x)
{
    st[x]=ed[x]=++dc;
    ord[dc]=x;
    if(!son[x])
        return;
    top[son[x]]=top[x];
    dfs2(son[x]);
    for(auto v:g[x])
    {
        if(v==fa[x]||v==son[x])
            continue;
        top[v]=v;
        dfs2(v);
    }
    ed[x]=dc;
}

struct T{
    int l,r,ls,rs;
    int s,a,b;
}t[N*2+1];

void update(int x)
{
    t[x].s=t[t[x].ls].s+t[t[x].rs].s;
}

void add(int x,int v)
{
    t[x].s+=t[x].a*v;
    t[x].b+=v;
}

void pushdown(int x)
{
    if(t[x].b)
    {
        add(t[x].ls,t[x].b);
        add(t[x].rs,t[x].b);
        t[x].b=0;
    }
}

int cnt;

int build(int l,int r)
{
    int x=++cnt;
    t[x].l=l,t[x].r=r;
    t[x].s=t[x].b=0;
    if(l==r)
    {
        t[x].a=w[ord[l]];
        return x;
    }
    int mid=(l+r)>>1;
    t[x].ls=build(l,mid);
    t[x].rs=build(mid+1,r);
    t[x].a=t[t[x].ls].a+t[t[x].rs].a;
    return x;
}

void change(int x,int l,int r,int v)
{
    if(l<=t[x].l&&t[x].r<=r)
    {
        add(x,v);
        return;
    }
    int mid=(t[x].l+t[x].r)>>1;
    pushdown(x);
    if(l<=mid)
        change(t[x].ls,l,r,v);
    if(r>mid)
        change(t[x].rs,l,r,v);
    update(x);
}

int qsum(int x,int l,int r)
{
    if(l<=t[x].l&&t[x].r<=r)
        return t[x].s;
    int mid=(t[x].l+t[x].r)>>1;
    pushdown(x);
    int ret=0;
    if(l<=mid)
        ret+=qsum(t[x].ls,l,r);
    if(r>mid)
        ret+=qsum(t[x].rs,l,r);
    return ret;
}

int Qsum(int x)
{
    int ret=0;
    while(x)
    {
        ret+=qsum(1,st[top[x]],st[x]);
        x=fa[top[x]];
    }
    return ret;
}

void Add(int x,int v)
{
    while(x)
    {
        change(1,st[top[x]],st[x],v);
        x=fa[top[x]];
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
            cin>>w[i],g[i].clear();
        for(int i=2;i<=n;i++)
        {
            int p;
            cin>>p;
            g[p].push_back(i);
        }
        dc=0;
        dfs1(1);
        top[1]=1;
        dfs2(1);
        cnt=0;
        build(1,n);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=Qsum(i);
            Add(i,1);
            if(i>=2)
                cout<<ans<<"\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 13820kb

input:

3
1 2 3
1 1
5
1 2 3 4 5
1 2 2 1

output:

1
2
1
3
5
4

result:

ok 6 numbers

Test #2:

score: -100
Runtime Error

input:

13
887 4555 8570 5485 8611 9500 295 2499 83 4959 9772 8620 3825
4 4 1 3 7 12 2 1 9 5 8 12
16
3405 9213 9243 8188 2733 1333 1614 4907 4256 7506 4228 1286 6121 6155 4082 8084
1 12 9 4 2 13 3 8 9 7 11 15 8 1 10
5
7183 1481 9468 8242 1044
1 5 5 1
3
5758 3693 1694
1 2
20
6683 4426 5616 8166 810 4265 3000...

output:


result: