QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#668390 | #7305. Lowest Common Ancestor | Afterlife# | RE | 3ms | 13820kb | C++20 | 2.8kb | 2024-10-23 14:12:01 | 2024-10-23 14:12:01 |
Judging History
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";
}
}
}
详细
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...