题意:一棵树,问不能再一条线上的三个点有多少种。
思路:先求出能在一条线上的三个点的种类数,然后拿C(n,3)减掉就是答案。求前面的值可以枚举中点,在此之前先dfs一边,算出所有节点的子节点个数。
吐槽:多校就这么结束了。。。。
#pragma comment(linker, "/STACK:16777216") #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n; int fst[100005],next[200005],node[200005],en,c[100005],pre[100005]; long long int ans,cnt,s; int dfs(int u,int p) { c[u]=1; pre[u]=p; if(next[fst[u]]==-1&&node[fst[u]]==p)return c[u]; for(int i=fst[u]; i!=-1; i=next[i]) { if(node[i]==p)continue; c[u]+=dfs(node[i],u); } return c[u]; } int main() { int u,v; while(scanf("%d",&n)!=EOF) { en=0; memset(fst,-1,sizeof(fst)); for(int i=1; i<n; i++) { scanf("%d%d",&u,&v); next[++en]=fst[u]; fst[u]=en; node[en]=v; next[++en]=fst[v]; fst[v]=en; node[en]=u; } dfs(1,-1); cnt=0; for(int i=1; i<=n; i++) { if(next[fst[i]]==-1)continue; s=0; for(int j=fst[i]; j!=-1; j=next[j]) { v=node[j]; if(pre[i]==v)s+=(1LL)*(n-c[i])*(c[i]-1); else s+=(1LL)*c[v]*(n-c[v]-1); } cnt+=s/2; } ans=(1LL)*n*(n-1)*(n-2)/6-cnt; printf("%I64d\n",ans); } return 0; }