变异蛮牛

很明显一道二分图染色问题，题目说黑点个数 - 包含的白点个数长度最大，因为在染色时候对于第一层我们默认是黑色的话，第二层的所有点就是白色，第三层就是黑色……依次类推，我们可以显然的发现长度最大只能是1,那么我们最后的个数就有两种情况$\backslash \backslash$ 1.从根结点到每个黑色的节点$\backslash \backslash$ 2.任意两个黑色节点的路径$\backslash \backslash$ 假设dfs完共有$ansans$个黑色节点，那么输出就是$ans+\left(\genfrac{}{}{0px}{}{2}{ans}\right)ans+\backslash tbinom\{2\}\{ans\}$

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<bits/stdc++.h>
# include<unordered_map>

# define eps 1e-9
# define fi first
# define se second
# define ll long long
# define int ll
# define x1 sb
# define y1 dsb
# define x2 ssb
# define y2 ddsb
// cout<<fixed<<setprecision(n) 
//bool operator<(const Node& x )
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=998244353;
const int N=2e5+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 
double e = exp(1);

int T,n,m,k,minn = inf,ans;
vector<int>g[N];
int a[N];
void dfs(int u,int v, int w){
	  a[u] = w;
	  if(a[u] == 1) ans++;
	  for(auto j : g[u]){
	  	   if(j == v) continue;
	  	   dfs(j,u,3-w);
	  }
}
void solve(){
         cin >> n;
         ans = 0;
         for(int i = 1 ; i <= n ; i ++ ) g[i].clear();
         for(int i = 1 ; i < n ; i ++ ){
		 	 int u,v;
		 	 cin >> u >> v;
		 	 g[u].push_back(v);
		 	 g[v].push_back(u);
		 }		
	     dfs(1,-1,1);	   
	     cout<<ans+ans*(ans-1)/2<<"\n";
}
/*

*/
signed main(){  
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
    cin >> T;
    // T = 1;
    while(T--){
		solve();
	} 
    return 0; 
}