QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#48449	#1288. Tokens on the Tree	Appleblue17	WA	100ms	8268kb	C++14	1.8kb	2022-09-13 18:00:29	2022-09-13 18:00:30

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-09-13 18:00:30]
评测

测评结果：WA
用时：100ms
内存：8268kb

查看

[2022-09-13 18:00:29]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long N=2e5+5,INF=1e9,mod=1e9+7,inv2=(mod+1)/2;
long long T,n,ans;
vector <long long> G[N];

long long mx[N],mx2[N],mx3[N];

void add(long long u,long long x){
	if(x>mx[u]) mx3[u]=mx2[u],mx2[u]=mx[u],mx[u]=x;
	else if(x>mx2[u]) mx3[u]=mx2[u],mx2[u]=x;
	else if(x>mx3[u]) mx3[u]=x;
}

long long FA[N],siz[N];
void dfs0(long long u,long long fa){
	siz[u]=1;
	FA[u]=fa;
	for(long long i=0;i<(long long)G[u].size();i++){
		long long v=G[u][i];
		if(v==fa) continue;
		dfs0(v,u);
		siz[u]+=siz[v];
		add(u,siz[v]); 
	}
	add(u,n-siz[u]);
}

long long S(long long x){
	return x*(x+1)/2%mod;
}
long long S2(long long x){
	return x*(x+1)/2*(2*x+1)/3%mod;
}
long long cal0(long long x,long long y){
	if(y<=x) return (S(x)*S(y)%mod*2%mod+mod-S(y)*S(y)%mod)%mod;
	else return S(x)*S(x)%mod;
}
long long cal(long long l,long long r,long long rr){
	return (cal0(r,rr)+mod-cal0(l-1,rr))%mod;
}

long long f[N];

int main(){
	cin>>T;
	while(T--){
		cin>>n; ans=0; 
		for(long long i=1;i<=n;i++) G[i].clear(),mx[i]=mx2[i]=mx3[i]=f[i]=0;
		for(long long i=2;i<=n;i++){
			long long x; cin>>x;
			G[i].push_back(x),G[x].push_back(i);
		}
		dfs0(1,0);
		long long MN=INF;
		for(long long i=1;i<=n;i++) MN=min(MN,mx[i]);
		
		
		for(long long u=1;u<=n;u++){
			long long sav=ans;
			for(long long i=0;i<(long long)G[u].size();i++){
				long long v=G[u][i];
				if(mx[v]<mx[u]) continue;
				if(v==FA[u]) ans=(ans+cal(mx[u]+1,mx[v],n-siz[u]))%mod;
				else ans=(ans+cal(mx[u]+1,mx[v],siz[v]))%mod;
			}
		}
		
		for(long long u=1;u<=n;u++){
			f[mx2[u]]=max(f[mx2[u]],mx3[u]);
		}
		for(long long i=n;i>=1;i--) f[i]=max(f[i],f[i+1]);
		
		for(long long i=1;i<=MN;i++){
			ans=(ans+2*cal(i,i,n-i))%mod;
			ans=(ans+mod-cal(i,i,f[i]))%mod;
		}
		
		cout<<ans<<endl;
	}
	
	
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 8268kb

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: 100ms

memory: 8256kb

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:

result:

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