UKE有哪些可能?
查看原帖
UKE有哪些可能?
590925
_x_y_楼主2023/7/12 14:12

好几篇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)
2023/7/12 14:12
加载中...