QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288001 | #7206. Triple | zjy0001 | WA | 2ms | 5908kb | C++14 | 4.4kb | 2023-12-21 14:59:00 | 2023-12-21 14:59:00 |
Judging History
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'