QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288001#7206. Triplezjy0001WA 2ms5908kbC++144.4kb2023-12-21 14:59:002023-12-21 14:59:00

Judging History

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

  • [2023-12-21 14:59:00]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5908kb
  • [2023-12-21 14:59:00]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define uint unsigned
#define LLL __int128_t
#define ldb long double
#define uLL unsigned long long
using namespace std;
char wS[262144],rdc[262144],*rS,*rT,*wT=wS;
#define gc() (rS==rT?rT=rdc+fread(rS=rdc,1,262144,stdin),rS==rT?EOF:*rS++:*rS++)
#define flush() fwrite(wS,1,wT-wS,stdout),wT=wS
inline void pc(const char&x){*wT++=x;if(__builtin_expect(wS+262144==wT,0))flush();}
template<class T=int>inline T read(){
    T x(0);char c;bool f(1);while(!isdigit(c=gc())&&c!=EOF)if(c==45)f=!f;
    if(c==EOF)return -1;
    if(f)do x=x*10+(c&15);while(isdigit(c=gc()));
    else do x=x*10-(c&15);while(isdigit(c=gc()));
    return x;
}
template<>inline char read(){char c;while((c=gc())<33);return c;}
template<>inline string read(){char c;string s;while((c=gc())<33);do s+=c;while((c=gc())>32);return s;}
inline int read(char*const s){char c,*t=s;while((c=gc())<33);do *t++=c;while((c=gc())>32);return *t=0,t-s;}
template<class T>inline void write(T x){
    int wtop=0;char wbuf[numeric_limits<T>::digits10+1];
    if(x>=0)do wbuf[wtop++]=(x%10)|48;while(x/=10);
    else{pc(45);do wbuf[wtop++]=-(x%10)|48;while(x/=10);}
    for(;wtop;pc(wbuf[--wtop]));
}
template<>inline void write(char x){pc(x);}
template<>inline void write(char*s){for(;*s;pc(*s++));}
template<>inline void write(const char*s){for(;*s;pc(*s++));}
template<>inline void write(string s){for(auto c:s)pc(c);}
template<class T,class...U>inline void write(const T&x,const U&...y){write(x),write(y...);}
const int N=1e5+5;
int n,lim,rt,Cn,Bn,tim;
bool vs[N];
LL ans,R[N];
vector<int>vec[N];
int Gm,Gh[N],Gv[N*2],Gnxt[N*2];
int sz[N],mx[N],len[N],son[N],f[N],id[N],L[N],U[N],B[N],S[N],h[N];
inline void add(const int&u,const int&v){
    Gv[++Gm]=v,Gnxt[Gm]=Gh[u],Gh[u]=Gm;
    Gv[++Gm]=u,Gnxt[Gm]=Gh[v],Gh[v]=Gm;
}
inline void dfs0(const int&u,const int&fa){
    sz[u]=1,mx[u]=0;
    for(int i=Gh[u],v;v=Gv[i];i=Gnxt[i])if(v!=fa&&!vs[v])
        dfs0(v,u),sz[u]+=sz[v],mx[u]=max(mx[u],sz[v]);
    if((mx[u]=max(mx[u],lim-sz[u]))<mx[rt])rt=u;
}
inline void dfs1(const int&u,const int&fa,const int&bl,const int&d){
    if(d>len[bl])len[bl]=d,vec[bl].emplace_back(0);
    ++vec[bl][d],sz[u]=1,son[u]=0;
    for(int i=Gh[u],v;v=Gv[i];i=Gnxt[i])if(v!=fa&&!vs[v])
        dfs1(v,u,bl,d+1),sz[u]+=sz[v],h[v]>h[son[u]]?son[u]=v:0;
    h[u]=h[son[u]]+1;
}
inline void dfs2(const int&u,const int&fa,const int&d){
    f[id[u]=++tim]=0,S[u]=0;
    if(son[u])dfs2(son[u],u,d+1),S[u]=S[son[u]];
    for(int i=Gh[u],v;v=Gv[i];i=Gnxt[i])
        if(v!=fa&&!vs[v]&&v!=son[u]){
            dfs2(v,u,d+1);
            int lst=0,suf=S[u],pre=0;
            for(int j=0;j<h[v]-d;++j)pre+=U[j];
            for(int j=0;j<h[v];++j)suf-=f[id[u]+j];
            for(int j=h[v];j;--j){
                int nw=f[id[u]+j],c=f[id[v]+j-1];
                ans+=L[max(0,j-d+1)]*(2ll*lst*nw+2ll*c*suf);
                suf+=nw,f[id[u]+j]+=c,S[u]+=c;
                if(j>d)ans+=pre*(2ll*lst*nw+2ll*c*suf),pre-=U[j-d-1];
                lst+=c;
            }
        }
    ans+=2ll*S[u]*L[0],f[id[u]]=1;
}
inline void solve(const int&u){
    Bn=0,L[0]=1,U[0]=1;
    int mxd=0;
    for(int i=Gh[u],v;v=Gv[i];i=Gnxt[i])if(!vs[v]){
        vec[v].emplace_back(len[v]=0);
        dfs1(v,u,v,1),B[++Bn]=v,mxd=max(mxd,len[v]);
        for(int d=len[v],nL=0;~d;--d)
            L[d]+=(nL+=vec[v][d]),U[d]+=vec[v][d],R[d]+=nL*(nL-1ll);
    }
    ans+=(L[1]*(L[1]-1ll)-R[1]);
    for(int i=1,v;v=B[i],i<=Bn;++i){
        for(int d=len[v],nL=0;~d;--d)
            L[d]-=(nL+=vec[v][d]),U[d]-=vec[v][d],R[d]-=(nL*(nL-1ll)),
            ans+=vec[v][d]*(L[d+1]*(L[d+1]-1ll)-R[d+1]);
        tim=0,dfs2(v,u,1);
        for(int d=len[v],nL=0;~d;--d)
            L[d]+=(nL+=vec[v][d]),U[d]+=vec[v][d],R[d]+=nL*(nL-1ll);
        vec[v].clear();
    }
    fill(L,L+mxd+1,0),fill(U,U+mxd+1,0),fill(R,R+mxd+1,0),vs[u]=1;
    for(int i=Gh[u],v;v=Gv[i];i=Gnxt[i])
        if(!vs[v]&&sz[v]>2)rt=0,lim=sz[v],dfs0(v,u),solve(rt);
}
inline void MAIN(){
    ans=0,Gm=0,fill(Gh+1,Gh+n+1,0),fill(vs+1,vs+n+1,0);
    for(int i=1;i<n;++i)add(read(),read());
    mx[rt=0]=1e9,lim=n,dfs0(1,0),solve(rt);
    write(n*(n-1ll)*(n-2)-ans,'\n');
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
#define LOCAL
#ifndef LOCAL
    freopen("reaction.in","r",stdin);
    freopen("reaction.out","w",stdout);
#endif
    while(~(n=read()))MAIN();
    return flush(),0;
}
/*
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5780kb

input:

3
1 2
2 3
4
1 2
2 3
2 4

output:

4
18

result:

ok 2 tokens

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 5908kb

input:

5
4 1
3 4
2 5
3 5
5
5 4
3 4
4 1
1 2
5
4 5
4 1
3 2
4 3
5
1 3
4 3
2 4
5 1
5
4 1
4 2
5 4
5 3
5
1 4
5 2
3 5
3 1
5
5 3
3 4
2 1
5 2
5
5 1
5 4
1 2
2 3
5
5 2
2 4
1 3
1 2
5
1 3
2 4
5 4
3 5
5
4 1
2 4
5 4
3 1
5
1 5
3 1
1 2
4 2
5
2 5
4 2
3 4
4 1
5
5 1
4 2
2 1
1 3
5
4 2
3 4
1 4
5 2
5
3 1
3 2
3 5
4 1
5
3 4
2 5
4 ...

output:

52
50
50
52
50
52
52
52
50
52
50
50
50
50
50
50
52
52
50
52
52
50
50
50
52
50
52
52
50
50
52
50
50
52
50
48
50
52
52
52
52
52
48
52
50
50
52
50
48
52
52
50
52
50
50
50
52
52
52
52
50
50
50
50
52
52
50
48
52
50
52
52
50
50
50
52
50
50
50
50
50
48
50
52
52
52
52
48
52
50
50
52
50
50
50
52
52
50
50
52
...

result:

wrong answer 1st words differ - expected: '40', found: '52'