ZJH and Monkeys

There are multiple test cases.

The first line of input contains an integer T, indicating the number of test cases.

For each test case:

The first line contains an integer n $(3 \leq n \leq 10^{5})$

In the next n-1 lines, each line contains two integers u_i and v_i $(1 \leq u_{i},v_{i} \leq n, u_{i} \ne v_{i})$ , denoting an edge between monkey u_iand monkey v_i.

C++11(clang++ 3.9) 解法, 执行用时: 284ms, 内存消耗: 11484K, 提交时间: 2020-02-29 13:24:15

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int t;
vector<int> vec[300005];
ll p1,p2;
void dfs(int u,int pre,int k)
{
	if(k%2) p1++;
	for(int i=0;i<vec[u].size();i++)
	{
		int v=vec[u][i];
		if(v!=pre) dfs(v,u,k+1);
	}
 } 
 int main()
 {
 	cin>>t;
 	while(t--)
 	{
 		p1=0;
 		p2=0;
 		cin>>n;
 		int u,v;
 		for(int i=1;i<n;i++)
 		{
 			scanf("%d%d",&u,&v);
 			vec[u].push_back(v);
 			vec[v].push_back(u);
		 }
		 dfs(1,0,0);
		 p2=n-p1;
		 ll ans=0;
		 if(n&1)
		 ans=p1*p2*p2*2+p1*p1*p2*2;
		 else
		 ans=p1*p1*n+p2*p2*n;
		 cout<<ans<<endl;
		 for(int i=1;i<=n;i++)
		 vec[i].clear();
	 }
	 return 0;
 }

详情