220726 T1 树染色问题 (树的直径)
2024-09-07 04:31:10
题目描述
高钧在校园中漫步时,经过了一棵树。这时,几个同学突然冒出来控制住了他。
这棵树有 nn 个节点, 每个节点有黑白两种颜色, 为了更好的 alb , 需要把所有节点染成同一种颜色。
为了更好的戏耍高钧,高钧被告知如果他在最短的时间内把这棵树的所有节点染成同一种颜色, 那他就不会被 alb。
高钧每次操作可以将一个同色连通块染成另一种颜色,他想知道他最少需要几次操 作才能把这棵树的所有节点染成同一种颜色。
对于树上的一个点集 SS , 它是这棵树的同色连通块当且仅当对于所有节点 i,j∈Si,j∈S,节点 ii 的颜色与节点 jj 的颜色相同且树上 ii 与 jj 简单路径上的所有点属于 SS 。
输入格式
第一行一个整数 nn 表示树的节点数。
第二行 nn 个整数 c_i∈ \{0,1 \}ci∈{0,1} 表示第 ii 个节点的初始颜色。
接下来 n-1n−1 行,每行两个整数 a_i,b_iai,bi,表示树上的一条边。
输出格式
输出一行一个整数,表示最少的操作次数。
先将原图缩点,再找出新树的直径的中心,以他为根,答案就是直径长度除以2。
1 #include <bits/stdc++.h>
2 //#define loveGsy
3 using namespace std;
4 const int N = 2e5 + 10;
5 vector<int> E[N];
6 int n, T, rt;
7 int col[N], d[N], a[N], b[N], bl[N];
8 int read() {
9 int x = 0, f = 1; char c = getchar();
10 while (c < '0'||c > '9') {if (c == '-') f = -1; c = getchar();}
11 while (c >= '0'&&c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
12 return x * f;
13 }
14
15 void dfs(int u, int f) {
16 if (col[u] == col[f]) bl[u] = bl[f];
17 else bl[u] = ++T;
18 for (int i = 0; i < (int)E[u].size(); i++) {
19 int t = E[u][i];
20 if (t == f) continue;
21 dfs(t, u);
22 }
23 }
24
25 void dfs1(int u, int f) {
26 d[u] = d[f] + 1;
27 if (d[u] > d[rt]) rt = u;
28 for (int i = 0; i < (int)E[u].size(); i++) {
29 int t = E[u][i];
30 if (t == f) continue;
31 dfs1(t, u);
32 }
33 }
34
35 int main() {
36 #ifdef loveGsy
37 freopen("tree.in", "r", stdin);
38 freopen("tree.out", "w", stdout);
39 #endif
40 n = read();
41 for (int i = 1; i <= n; i++) col[i] = read();
42 for (int i = 1; i < n; i++) {
43 a[i] = read(), b[i] = read();
44 E[a[i]].push_back(b[i]); E[b[i]].push_back(a[i]);
45 }
46 col[0] = col[1] ^ 1;
47 dfs(1, 0);
48 for (int i = 1; i <= n; i++) E[i].clear();
49 for (int i = 1; i < n; i++) {
50 int x = bl[a[i]], y = bl[b[i]];
51 if (x != y) E[x].push_back(y), E[y].push_back(x);
52 }
53 dfs1(1, 0);
54 int x = rt; rt = 0;
55 dfs1(x, 0);
56 printf("%d\n", d[rt] / 2);
57 return 0;
58 }
最新文章
- linux下centos的网络连接
- react 15来了
- Windows上python的virtualenv 安装及使用
- 如果我可以重新学习iOS开发(转)
- VS2012网布网站与IIS配置
- Fishnet(暴力POJ 1408)
- C#_抓包HttpWebRequest跟HttpWebResponse
- 漫谈iOS Crash收集框架
- MFC error C2065: “IDD_DIALOG1” : 未声明的标识符 转载
- 有关linux标准输出、标准输入、标准错误的重定向问题
- 四维dp 或者 剪枝 + dfs Codeforces Beta Round #6 (Div. 2 Only) D
- webService 下得 拦截
- Flink从Kafka 0.8中读取多个Topic时的问题
- 百度搜索(jsonp)
- Vuex初级入门及简单案例
- 文本分类实战(七)—— Adversarial LSTM模型
- 18年最有";钱";途的专业就是它(文末有福利)
- tput
- JS中的数学方法
- ESP32 ADC
热门文章
- 第十七天python3 文件IO(三)
- .NET的求复杂类型集合的差集、交集、并集
- vscode 个人配置 settings.json
- 天人合一物我相融,站点升级渐进式Web应用PWA(Progressive Web Apps)实践
- 2. 组复制技术架构 | 深入浅出MGR
- 完整代码:AgileFontSet迅捷字体设置程序
- Linux系列之压缩命令
- Luogu[YNOI2019]排序(DP,线段树)
- mybatis-plus 生成全套crud
- Excelize 2.3.1 发布,Go 语言 Excel 文档基础库,支持加密表格文档