QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210537#6538. Lonely Kingucup-team1004WA 3ms18356kbC++143.1kb2023-10-11 16:14:462023-10-11 16:14:46

Judging History

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

  • [2023-10-11 16:14:46]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:18356kb
  • [2023-10-11 16:14:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=2e5+10,INF=1e9;
int n,a[N],b[N];
vector<int>to[N];
int fa[N],dep[N],son[N],siz[N],top[N];
int Max(int x,int y){
	return dep[x]>dep[y]?x:y;
}
int Min(int x,int y){
	if(a[x]^a[y])return a[x]<a[y]?x:y;
	else return Max(x,y);
}
void dfs1(int u){
	b[u]=to[u].size();
	dep[u]=dep[fa[u]]+1,siz[u]=1;
	for(int v:to[u]){
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
int dft,dfn[N],pos[N];
void dfs2(int u,int t){
	top[u]=t,pos[dfn[u]=++dft]=u;
	if(son[u])dfs2(son[u],t);
	for(int v:to[u])if(v^son[u])dfs2(v,v);
}
int t[N<<2],v[N<<2];
void pushup(int rt){
	t[rt]=Min(t[rt<<1],t[rt<<1|1]);
	v[rt]=Max(v[rt<<1],v[rt<<1|1]);
}
bool chk(int u){
	return b[u]>(u!=1);
}
void build(int l=1,int r=n,int rt=1){
	if(l==r){
		t[rt]=chk(pos[l])?pos[l]:0;
		v[rt]=l>1?0:1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void erase(int x,int l=1,int r=n,int rt=1){
	if(l==r){
		t[rt]=0;return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)erase(x,l,mid,rt<<1);
	else erase(x,mid+1,r,rt<<1|1);
	pushup(rt);
}
void insert(int L,int R,int l=1,int r=n,int rt=1){
	if(l==r){
		v[rt]=pos[l];return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)insert(L,R,l,mid,rt<<1);
	if(mid<R)insert(L,R,mid+1,r,rt<<1|1);
	pushup(rt);
}
int query(int L,int R,int l=1,int r=n,int rt=1){
	if(L<=l&&r<=R)return t[rt];
	int mid=(l+r)>>1,s=0;
	if(L<=mid)s=Min(s,query(L,R,l,mid,rt<<1));
	if(mid<R)s=Min(s,query(L,R,mid+1,r,rt<<1|1));
	return s;
}
int find(int L,int R,int l=1,int r=n,int rt=1){
	if(L<=l&&r<=R)return v[rt];
	int mid=(l+r)>>1,s=0;
	if(L<=mid)s=Max(s,find(L,R,l,mid,rt<<1));
	if(mid<R)s=Max(s,find(L,R,mid+1,r,rt<<1|1));
	return s;
}
ll ans;
void solve(int u){
	int p=0,q=0;
	for(int x=u;x;x=fa[top[x]]){
		q=Max(q,find(dfn[top[x]],dfn[x]));
	}
	for(int x=u;x;x=fa[top[x]]){
		if(top[x]^top[q]){
			p=Min(p,query(dfn[top[x]],dfn[x]));
		}else{
			p=Min(p,query(dfn[q],dfn[x]));break;
		}
	}
	// debug(u,p,q);
	ans+=1ll*a[u]*a[p];
	for(int x=u;p^x;x=fa[top[x]]){
		if(top[x]^top[p]){
			insert(dfn[top[x]],dfn[x]);
		}else{
			insert(dfn[p]+1,dfn[x]);break;
		}
	}
	if(b[p]--,!chk(p)){
		// debug("ers",p);
		erase(dfn[p]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%d",&fa[i]),to[fa[i]].push_back(i);
		// debug(fa[i],i);
	}
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	a[0]=INF;
	dfs1(1),dfs2(1,1);
	vector<int>t;
	for(int i=2;i<=n;i++){
		if(!b[i])t.push_back(i);
	}
	sort(t.begin(),t.end(),[](int x,int y){
		return a[x]>a[y];
	});
	build();
	for(int x:t)solve(x);
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
1 1 2
2 1 3 2

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: 0
Accepted
time: 0ms
memory: 13992kb

input:

50
1 2 1 1 2 1 6 3 7 5 11 11 8 10 7 8 9 7 17 2 18 4 23 8 17 21 3 19 2 4 21 18 1 26 21 36 26 24 7 7 29 27 19 29 36 11 29 42 21
15 31 15 40 15 33 2 33 15 6 50 48 33 6 43 36 19 37 28 32 47 50 8 26 50 44 50 31 32 44 22 15 46 11 33 38 22 27 43 29 8 1 21 31 28 26 39 29 39 42

output:

22728

result:

ok 1 number(s): "22728"

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 18356kb

input:

500
1 1 2 4 3 1 7 2 8 10 8 12 1 7 11 9 14 18 1 17 9 1 16 17 6 14 17 1 26 25 26 29 6 8 7 15 32 9 27 11 34 31 35 6 25 4 35 40 12 2 39 34 21 8 48 8 49 1 39 32 30 46 10 1 45 29 2 17 31 22 30 16 59 10 63 15 71 53 28 50 46 29 59 53 5 3 5 83 48 50 39 18 24 76 6 65 28 72 81 38 54 8 35 88 89 89 18 99 9 99 76...

output:

153274586146

result:

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