好几篇RemoteJudge的题都是UKE 下面这个代码在其他网站上过了,为什么UKE呢?
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
int ver[N * 2], head[N], nxt[N * 2], tot;
void add(int x, int y){
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
int n;
int cnt[2];
bool vis[N];
int d[N], sz[N];
void dfs(int x){
vis[x] = 1;
cnt[d[x] % 2]++;
sz[x] = 1;
for(int i = head[x]; i; i = nxt[i]){
int y = ver[i];
if(vis[y])
continue;
vis[y] = 1;
d[y] = d[x] + 1;
dfs(y);
sz[x] += sz[y];
}
}
int main(){
cin >> n;
for(int i = 1; i <= n - 1; i++){
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs(1);
long long ans = 0;
for(int i = 1; i <= n; i++)
ans += 1ll * sz[i] * (n - sz[i]);
ans += 1ll * cnt[0] * cnt[1];
cout << ans / 2 << endl;
return 0;
}
小猴编程(2971533446508572)