题面

对于给定的树T，计算集合{A，B，C}的数量，其中：

1、A，B，C是树T的节点

2、不存在经过A，B，C的简单路径

分析

我猜题目叫Y的原因是因为要求的三个点构成一个Y的形状qvq

先看这个粉色的部分，考虑怎么计算第二部分的答案呢？

根据组合数学的思想，可以从3,4,8为根的子树内选两个（一个子树内只能选一个），然后再从除了以2为根的子树的其他所有结点中选一个，相乘。

第一部分的答案就更简单了，就是这个子树的所有小子树的大小的乘积，因为会被三次计算，所以最后除以三

然而！！

上面的方法过于复杂，我们可以根据正难则反的思想。计算三个点在一个简单路径上的数量，再用总路径数C(N,3)减去它。

三个点在一个简单路径：对于有儿子的点，选择他，并在以他为根的子树中选1个和除了他的子树以外的所有点中选1个

对于无儿子的点，除了他的所有点中选择2个。

最后因为每条路径被三个点计算了，总简单路径数除以3

代码

法一的代码。法二的代码更为简洁，可以自行实现

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define ll long long #define N 200010ll t,n,p1,p2,cnt;ll first[N],siz[N];struct email{    ll u,v;    ll nxt;}e[N*4];inline void add(ll u,ll v){    e[++cnt].nxt=first[u];first[u]=cnt;    e[cnt].u=u;e[cnt].v=v;}inline void init(){    cnt=p1=p2=0;    memset(siz,0,sizeof(siz));    memset(first,0,sizeof(first));    }void dfs(ll u,ll fa){    ll mulv=0;siz[u]=1;    for(ll i=first[u];i;i=e[i].nxt)    {        ll v=e[i].v;        if(v==fa)continue;        dfs(v,u);        mulv+=(siz[u]-1)*(siz[v]);        siz[u]+=siz[v];    }    p1+=mulv*(n-siz[u]);    for(ll i=first[u];i;i=e[i].nxt)    {        ll v=e[i].v;        if(v==fa)continue;        p2+=siz[v]*(mulv-siz[v]*(siz[u]-1-siz[v]));    }}int main(){    while(scanf("%lld",&n)==1)    {        init();        for(ll i=1;i