NC231934. 变异蛮牛
描述
幽怨火，憎恨焰，变异蛮牛续执念。
输入描述
全文第一行是，表示数据组数；
接下来组数据，先输入一行一个正整数表示树的大小
；
接下来输入行每行两个正整数
表示树的一条边。
输出描述
输出
示例1
输入:
1 6 1 2 2 3 3 4 4 5 5 6
输出:
6
说明:
合法的链分别是：C++ 解法, 执行用时: 443ms, 内存消耗: 21124K, 提交时间: 2022-01-21 19:30:39
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int i,j,k,n,m,t,it;
ll res;
vector<int> v[200500];
void dfs(int x,int fa,int y){
if(y)res+=++it;
for(auto i:v[x]){
if(i!=fa)dfs(i,x,y^1);
}
}
int main() {
ios::sync_with_stdio(0);
cin>>t;
while(t--){
cin>>n;
res=0;it=0;
for(i=1;i<=n;i++){
v[i].clear();
}
for(i=1;i<n;i++){
cin>>j>>k;
v[j].push_back(k);
v[k].push_back(j);
}
dfs(1,0,1);
cout<<res<<'\n';
}
}