题意

题目链接。

给你一棵树，你可以在树上连两条边，这两条边会分别形成两个环，要求这两个环没有任何相同的边或结点，求连边的方案数。

解析

蛮有趣的一个树形 dp。

考虑对于所有的连边方案，在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ，有多少方案是以其为 LCA 的，发现共有以下几种情况：

1. $2-2$ 结构：在 $u$ 的两棵不同子树中分别连一条边，显然这两条边形成的环不会有共同点，且以该点为 LCA.
2. $3-1$ 结构：在 $u$ 的一棵子树中，连一条边再找一个点 $x$，满足 $x$ 到 $u$ 的路径中不会与连的那一条边有任何相交；再在另一棵子树中找一个点（这个点也可以是 $u$ 点），与点 $x$ 连边。
3. $2-1-1$ 结构：在 $u$ 的一颗子树中连一条边，再在另两棵子树中各找一个点（这两个点中也可以有 $u$ 点），把这两个点相连。

根据上述分类，我们先做一些辅助工作：

1. 我们记 $f_u$ 为以 $u$ 为树根的子树中，有多少种连一条边的方案（本质上为 $C_{siz}^2$），容易用 dp 得到。

2. 我们记 $g_u$ 为以 $u$ 为树根的子树中，有多少种连一条边再找一个点，并满足该点到点 $u$ 不会与那条边相交的情况。那么有这些合法情况：

   1. 边和点都在同一棵子树内。
   2. 边在一颗子树内，点为 $u$ 节点。
   3. 边在一颗子树内，点在另一棵子树内。

   这样我们就可以通过 dp 计算出 $g_u$​.

最后，我们就可以在每一个点更新出以该点为 LCA 的答案，分别计算前面提到的三种结构的贡献即可，代码细节仍有一些复杂，这里不做赘述，可以参考下文的实际代码。

代码

#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=5e5+5;
const int M=1e6+5;
struct node{
    int to,nxt;
}e[M];
int head[N],cnt;
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int T,n;
ll ans,f[N],siz[N],g[N];
void dfs(int u,int fa,int depth){
    siz[u]=1;ll totalf=0,total2=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa) continue;
        dfs(v,u,depth+1);
        f[u]+=f[v];f[u]+=siz[v]*siz[u];//f_u dp
        g[u]+=g[v];g[u]+=f[v];//g_u dp 情况1,2
        ans+=f[v]*totalf;//2-2 结构 
        totalf+=f[v];total2+=siz[v]*(siz[u]-1);
        siz[u]+=siz[v];
    }
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa) continue;
        g[u]+=siz[v]*(totalf-f[v]);//g_u dp 情况3
        ans+=f[v]*(total2-siz[v]*(siz[u]-1-siz[v]));//2-1-1 结构中不含 u 点的情况
        ans+=f[v]*(siz[u]-1-siz[v]);//2-1-1 结构中含 u 点的情况
        ans+=g[v]*(siz[u]-siz[v]);//3-1 结构
    }
}
void solve(){
    scanf("%d",&n);cnt=0;ans=0;
    for(int i=1;i<=n;i++) head[i]=f[i]=siz[i]=g[i]=0;
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,1,1);
    printf("%lld\n",ans);
}
signed main(){
    scanf("%d",&T);
    while(T--) solve();    
    return 0;
}