Codeforces 862B(DFS黑白染色)

Codeforces 862B
题意:给出一个树,树的每一条边$(u,v)$将$u, v$分成两个集合互不相交,问能做多添加多少条边使得添加后的图还是每一条边$(u,v)$将$u, v$分成两个集合互不相交。

对于图黑白染色即可。
意思即为,从一个点遍历,这个点为白色,然后找它的连点,视为黑色,最后统计白色,黑色节点的个数$b, w$,答案即为$b \times w - (n - 1)$

也可以直接dfs求出深度判深度奇偶性,计算公式和上述算法一样

注意全部开LL,包括中间变量

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
//cf only
#define rd(a) scanf("%d", &a)
#define rd2(a, b) scanf("%I64d%I64d", &a, &b)
#define pty printf("YES\n")
#define ptn printf("NO\n")
#define pt(x) printf("%I64d\n", x)
#define pts(x) printf("%I64d ", x)
using namespace std;
int read() {
int x=0;char ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}
LL n, dep[100000 + 5];
vector<int> G[100000 + 5];
void dfs(int u, int pa) {
dep[u] = dep[pa] + 1;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) dfs(v, u);
}
}
void clean() {
ms(dep, 0);
}
void solve() {
clean();
for (LL i = 1; i < n; i++) {
LL u ,v ; rd2(u, v);
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, 0);
LL js = 0, os = 0;
for (LL i = 1; i <= n; i++) {
if (dep[i] % 2 == 0) os++; else js++;
}
pt(os * js - (n - 1));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("2.out", "w", stdout);
#endif
rd(n), solve();
return 0;
}

------ 本文结束 ------