QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#725997 | #1288. Tokens on the Tree | six-floor-slip-liu | WA | 13ms | 5960kb | C++20 | 3.0kb | 2024-11-08 21:09:30 | 2024-11-08 21:09:31 |
Judging History
answer
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
int n;
vector<int> e[N],vec[N];
int sz[N],mx[N];
int rt;
int pmx[N];
void dfs(int x,int fa){
sz[x]=1;mx[x]=0;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
mx[x]=max(mx[x],sz[i]);
sz[x]+=sz[i];
vec[x].push_back(sz[i]);
}
mx[x]=max(mx[x],n-sz[x]);
vec[x].push_back(n-sz[x]);
sort(vec[x].begin(),vec[x].end(),greater<int>());
if(mx[x]<=n/2){
rt=x;
}
}
int calc(int l,int r){
if(l>r) return 0;
return (1ll*(r-l+1)*(l+r)/2)%mod;
}
vector<int> add[N],del[N];
int ff[N];
void dfs2(int x,int fa){
ff[x]=fa;sz[x]=1;
for(auto i:e[x]){
if(i==fa) continue;
dfs2(i,x);
sz[x]+=sz[i];
}
}
void solve(){
n=read();
forup(i,1,n){
e[i].clear();
add[i].clear();del[i].clear();
vec[i].clear();
pmx[i]=0;
}
forup(i,2,n){
int f=read();
e[i].push_back(f);
e[f].push_back(i);
}
rt=0;
dfs(1,0);
dfs2(rt,0);
int m=vec[rt][0];
forup(u,1,n){
if(vec[u].size()>=3){
pmx[vec[u][1]]=max(pmx[vec[u][1]],vec[u][2]);
}
if(mx[u]==m) continue;
add[mx[ff[u]]+1].push_back(sz[u]);
del[mx[u]+1].push_back(sz[u]);
}
int ans=0;
fordown(i,n,1){
pmx[i]=max(pmx[i],pmx[i+1]);
}
forup(i,1,n){
msg("%d ",pmx[i]);
}msg("|\n");
forup(w,1,m){
(ans+=2ll*calc(1,min(w-1,pmx[w]))%mod*w%mod)%=mod;
(ans+=4ll*calc(pmx[w]+1,w-1)%mod*w%mod)%=mod;
if(w<=pmx[w]) (ans+=1ll*w*w%mod)%=mod;
else (ans+=2ll*w*w%mod)%=mod;
msg("%d %d|\n",w,ans);
}
int val=0;
for(auto i:add[m]){
(val+=calc(1,i))%=mod;
msg("{%d %d}\n",m,i);
}
for(auto i:del[m]){
val=(val+mod-calc(1,i))%mod;
msg("{%d %d}\n",m,-i);
}
forup(w,m+1,n-1){
for(auto i:add[w]){
(val+=calc(1,i))%=mod;
msg("{%d %d}\n",w,i);
}
for(auto i:del[w]){
val=(val+mod-calc(1,i))%mod;
msg("{%d %d}\n",w,-i);
}
(ans+=2ll*w*val%mod)%=mod;
msg("%d %d|\n",w,ans);
}
printf("%d\n",ans);
}
signed main(){
int t=read();
while(t--){
solve();
}
}
/*
2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5876kb
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: 13ms
memory: 5960kb
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'