QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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
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;
}
}
Details
Tip: Click on the bar to expand more detailed information
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:
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'