QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#26637#1288. Tokens on the TreeWu_RenWA 28ms10004kbC++171.9kb2022-04-07 20:30:152022-04-29 04:08:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 04:08:33]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:10004kb
  • [2022-04-07 20:30:15]
  • 提交

answer

#include <bits/stdc++.h>
const int mod=1e9+7;
using namespace std;
int n,head[200010],fa[200010],o,m;
int mx[200010],se[200010],th[200010],lim[200010],sz[200010],f[200010],ans;
struct edge{
	int to,link;
}e[400010];
void qmo(int &x){
	x+=(x>>31)&mod;
}
void add_edge(int u,int v){
	e[++o]={v,head[u]},head[u]=o;
	e[++o]={u,head[v]},head[v]=o;
}
void dfs(int u,int pre){
	sz[u]=1,fa[u]=pre;
	mx[u]=se[u]=th[u]=-2e9;
	for(int i=head[u],v;i;i=e[i].link) if((v=e[i].to)^pre){
		dfs(v,u),sz[u]+=sz[v];
		if(sz[v]>=mx[u]) th[u]=se[u],se[u]=mx[u],mx[u]=sz[v];
		else if(sz[v]>=se[u]) th[u]=se[u],se[u]=sz[v];
		else if(sz[v]>th[u]) th[u]=sz[v];
	}
	if(pre){
		if(n-sz[u]>=mx[u]) th[u]=se[u],se[u]=mx[u],mx[u]=n-sz[u];
		else if(n-sz[u]>=se[u]) th[u]=se[u],se[u]=n-sz[u];
		else if(n-sz[u]>th[u]) th[u]=n-sz[u];
	}
	m=min(m,mx[u]);
	if(se[u]>0) lim[se[u]]=max(lim[se[u]],th[u]);
} 
int get(int wl,int bl){//w<=wl,b<=bl,w>=b
	bl=min(bl,wl);
	if(bl==wl){
		return f[wl];
	}
	int res=bl*(bl+1ll)%mod*((wl-bl)*(wl+bl+1ll)/2%mod)%mod;
	qmo(res+=get(bl,bl)-mod);
	return res;
}
void sol(){
	scanf("%d",&n),o=0,m=2e9,ans=0;
	for(int i=1;i<=n;i++) head[i]=0;
	for(int i=2,w;i<=n;i++) scanf("%d",&w),add_edge(w,i);
	for(int i=1;i<=n;i++) f[i]=(f[i-1]+1ll*i*i%mod*i)%mod,lim[i]=0;
	dfs(1,0);
	for(int i=n;i>=1;i--) lim[i]=max(lim[i+1],lim[i]);
	if(m>=1){
		int w=m*(m+1ll)/2%mod;
		ans=2ll*w*w%mod;
		for(int w=1;w<=m;w++){
			int b=min(w,lim[w]);
			qmo(ans-=b*(b+1ll)/2%mod*w%mod);
			b=min(w-1,lim[w]);
			qmo(ans-=b*(b+1ll)/2%mod*w%mod);
		}
	}
	for(int u=1;u<=n;u++){
		int mxx=0,Up=-1,o;
		for(int i=head[u],v;i;i=e[i].link) if(mx[v=e[i].to]<=mx[u]&&mx[v]>mxx) Up=v,mxx=mx[v],o=(v==fa[u]?sz[u]:n-sz[v]);
		mxx=max(mxx,m);
		if(mxx<mx[u]&&Up>0) qmo(ans+=get(mx[u],o)-mod),qmo(ans-=get(mxx,o));
	}
	printf("%d\n",ans);
}
int main(){
	int _;
	scanf("%d",&_);
	while(_--) sol();

}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 9928kb

input:

2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2

output:

71
989

result:

ok 2 tokens

Test #2:

score: -100
Wrong Answer
time: 28ms
memory: 10004kb

input:

33327
10
1 2 3 4 5 2 7 8 2
7
1 2 3 4 5 2
8
1 2 3 4 5 3 1
2
1
7
1 2 3 3 3 1
5
1 2 2 1
5
1 2 3 1
2
1
4
1 2 2
8
1 2 3 4 5 5 4
9
1 2 3 1 5 6 7 8
5
1 1 3 4
8
1 2 3 3 5 5 5
8
1 2 2 2 1 6 1
6
1 2 3 2 5
7
1 2 3 4 3 2
5
1 2 3 3
4
1 1 1
6
1 1 3 4 4
3
1 2
10
1 2 1 4 5 5 7 7 9
2
1
3
1 2
6
1 1 3 4 5
7
1 2 3 1 5 ...

output:

981
253
421
1
251
71
70
2
31
423
660
70
419
419
141
255
71
31
141
10
997
1
9
140
252
10
71
2
2
675
423
1007
71
70
140
429
30
667
10
945
655
70
661
10
10
70
31
255
141
71
255
669
30
252
2
30
419
255
661
427
10
421
2
659
141
993
30
141
417
10
2
423
141
30
667
675
417
71
421
255
10
140
675
2
30
2
31
30...

result:

wrong answer 4th words differ - expected: '2', found: '1'