#牛客小白月赛44-变异蛮牛#
变异蛮牛
https://ac.nowcoder.com/acm/contest/11221/E
合法链只有起始端都是黑点的情况（包括单个黑点）链的长度都是1
- 设黑点总数为ans 则答案=(ans+1)*ans
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;
vector<int>g[N];
ll ans;
int dfs(int f, int depth, int ff){
ll sum = depth%2==0?1:0;
for(auto to : g[f]){
if(to!=ff)
sum += dfs(to, depth+1, f);
}
return sum;
}
void solve(){
int n, f, to, i;
cin >> n;
for(i=1; i<=n; i++){
g[i].clear();
}
for(i=1; i<n; i++){
cin >> f >> to;
g[f].push_back(to);
g[to].push_back(f);
}
ans = dfs(1, 0, -1);
cout << ans + (ans-1)*ans/2 << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
投递美团等公司8个岗位
你如果觉得你的实习经历质量不够可以找我之前跟的老师，可以包装大厂项目，这样你还有更多机会