Submission #44099745

---

Source Code Expand

#include<cstdio>
#include<cstring>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
// #define add(a,b) (a+=b)>=mod&&(a-=mod)
#define sub(a,b) (a-=b)<0&&(a+=mod)
const int N=200010,M=400010;
namespace IO{
	const char fg=' ';
	int len=0;
	char ibuf[(1<<20)+1],*iS,*iT,out[(1<<25)+1],ar[50];
	#define gh()\
	(iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),\
	(iS==iT?EOF:*iS++):*iS++)
	#define putc(ch) out[len++]=ch
	void read(){}
	template<typename Type,typename...Types>
	void read(Type&x,Types&...xs){
		x=0;
		char ch=gh();
		char t=0;
		while(ch<'0'||ch>'9')t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=gh();
		x=t?-x:x;
		read(xs...);
	}
	template<typename Type>
	void write(Type&x){
		int tot=0;
		if(!x)putc('0');
		if(x<0)putc('-'),x=-x;
		while(x)ar[++tot]=x%10+'0',x/=10;
		for(int i=tot;i;--i)putc(ar[i]);
		putc(fg);
	}
	void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
}
typedef long long ll;
using namespace IO;
int n,e[M],h[N],ne[M],sz,idx;
ll ans;
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int x,int fa){
	int sz=1;
	for(int i=h[x];~i;i=ne[i]){
		int j=e[i];
		if(j==fa)continue;
		ll tmp=dfs(j, x);
		sz+=tmp;
		ans+=tmp*(n-tmp);
		// printf("j:%d,ans=%lld,ans=%lld\n",j,tmp*(n-tmp),ans);
	}
	return sz;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	#endif
	// Insert Code Here
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	read(n);
	memset(h,-1,n*4+4);
	E(i, n-1){
		int a,b;
		read(a,b);
		add(a,b),add(b,a);
	}
	dfs(1,-1);
	ans=ans-(n*(n-1ll)>>1);
	// printf("%lld\n",ans);
	ans=n*(n-1ll)*(n-2)/6-ans;
	write(ans);
	flush();
	return 0;
}

Submission Info

Judge Result