小O的树上加边
小O的树上加边
https://www.nowcoder.com/practice/246a42faded9456d964ddbc55a79e33c
小O的树上加边
[题目链接](https://www.nowcoder.com/practice/246a42faded9456d964ddbc55a79e33c)
思路
树是一个天然的二分图。要在保持二分图性质的前提下，求最多能加多少条边。
二分图的最大边数
对树做黑白染色（BFS/DFS），将所有节点分成两个集合，大小分别为 和
（
）。二分图中，所有边只能连接两个不同集合的节点，因此完全二分图
的边数为
。
树本身有 条边，所以最多还能加的边数为：
$$
如何求 
和 
从任意节点出发做 BFS，交替染色。统计两种颜色各有多少节点即可。
样例演示
4 个节点的链 ，染色后集合为
和
，大小均为 2。完全二分图边数
，减去已有的
条边，答案为
（即添加边
）。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
vector<vector<int>> g(n+1);
for(int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> color(n+1,-1);
queue<int> q;
color[1]=0;
q.push(1);
long long cnt[2]={0,0};
while(!q.empty()){
int u=q.front();q.pop();
cnt[color[u]]++;
for(int v:g[u]){
if(color[v]==-1){
color[v]=1-color[u];
q.push(v);
}
}
}
printf("%lld\n", cnt[0]*cnt[1]-(n-1));
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
g.get(u).add(v);
g.get(v).add(u);
}
int[] color = new int[n + 1];
Arrays.fill(color, -1);
color[1] = 0;
Queue<Integer> q = new LinkedList<>();
q.add(1);
long[] cnt = new long[2];
while (!q.isEmpty()) {
int u = q.poll();
cnt[color[u]]++;
for (int v : g.get(u)) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.add(v);
}
}
}
System.out.println(cnt[0] * cnt[1] - (n - 1));
}
}
查看20道真题和解析