思路

首先思考一下，满足那些条件的三个点不会在一条路上？以任意一个点为根节点，它的三个不同子树上的三个点不在一条路上 （读者自证不难），那直接找就对了。先预处理出以$1$为根节点时每一个点的子树大小，再跑一遍dfs找答案就好了，具体做法如下：

对于遍历一个点的时候，定义$a$,$b$,$c$，分别表示这个点目前访问的子节点中选中一个点、两个点、三个点的方案数，转移时大致如下（$k$为当前子树的大小）：

最后$ans+c$即可

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,siz[N],ans;
vector<int>G[N];
void dfs1(int x,int xfa)
{
	siz[x]=1;
	for(int i:G[x])if(i!=xfa)
	{
		dfs1(i,x);
		siz[x]+=siz[i];
	}
}
void dfs2(int x,int xfa)
{
	int a=0,b=0,c=0;
	for(int i:G[x])
	{
		int k=0;
		if(i!=xfa)
		{
			dfs2(i,x);
			k=siz[i];
		}
		else k=n-siz[x];
		c+=k*b;
		b+=k*a;
		a+=k;
	}
	ans+=c;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,0);
	printf("%lld\n",ans);
	return 0;
}