QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725997#1288. Tokens on the Treesix-floor-slip-liuWA 13ms5960kbC++203.0kb2024-11-08 21:09:302024-11-08 21:09:31

Judging History

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

  • [2024-11-08 21:09:31]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:5960kb
  • [2024-11-08 21:09:30]
  • 提交

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'