可以得到题目要求的是$\sum_{a,b无祖先关系} \max(dis(a,b)-|dep_a-dep_b|-1,0)$，然后我转化成了代码中的式子

#include <bits/stdc++.h>
using namespace std;
const int N=300007;
long long sz[N],a[N],s[N],d[N],f[N],ans,n;
vector<int> to[N];
void dfs(int o,int fa){
	sz[o]=1;
	a[d[o]]++;
	f[o]=1ll*sz[o]*(sz[o]-1)/2;
	for(auto i:to[o]) if(i!=fa) d[i]=d[o]+1,dfs(i,o),sz[i]+=sz[o],f[o]-=1ll*sz[i]*(sz[i]-1)/2;
	ans+=1ll*sz[o]*(n-sz[o]);
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t-->0){
		cin>>n;
		for(int i=1;i<=n+1;i++) to[i].clear(),a[i]=0;
		for(int i=1,u,v;i<n;i++) cin>>u>>v,to[u].push_back(v),to[v].push_back(u);
		ans=0;
		dfs(1,0);
		for(int i=n;i;i--) s[i]=s[i+1]+a[i];
		for(int i=1;i<=n;i++) ans-=1ll*a[i]*s[i+1];
		ans-=n*(n-1)/2;
		cout<<ans<<'\n';
	}
	return 0;
}