变异蛮牛 树，dfs，二分图染色 牛客白月赛44

链接：https://ac.nowcoder.com/acm/contest/11221/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
幽怨火，憎恨焰，变异蛮牛续执念。

给定一棵根为 11，且是黑点的有根树。

每个白点相邻所有的点都是黑点，每个黑点相邻所有的点都是白点。换句话说，你可以从根结点开始，按照深度对每个点黑白染色。

现在对于一条两个端点分别是 u,vu,v 的链，定义其长度为：包含的黑点个数 -− 包含的白点个数。

请你数一数 长度最大 的链的个数。
输入描述:
全文第一行是 T(1\le T\le10^5)T(1≤T≤10
5
)，表示数据组数；

接下来 TT 组数据，先输入一行一个正整数表示树的大小 n(1\le n\le2\times10^5,\sum n\le3\times10^6)n(1≤n≤2×10
5
,∑n≤3×10
6
)；

接下来输入 n-1n−1 行每行两个正整数 u,v(1\le u,v\le n)u,v(1≤u,v≤n) 表示树的一条边。
输出描述:
输出 TT 行，每行一个整数表示答案。
示例1
输入
复制
1
6
1 2
2 3
3 4
4 5
5 6
输出
复制
6
说明
合法的链分别是：{1},{3},{5},{1,2,3},{3,4,5},{1,2,3,4,5}{1},{3},{5},{1,2,3},{3,4,5},{1,2,3,4,5}。

思路 ：

• 显然这棵树第一层全黑，第二层全白，第三层全黑…因此，黑 - 白数量最多为1，要么就选一个黑点，要么就选起始皆为黑点，假设黑点个数为cnt，则答案为$cnt+C_{cnt}^2$
• 值得注意的是，最后输出公式中加法的两个部分都要先乘上1ll，否则会wa
• 优化：每次清空边动态数组时，只要清理本次样例的范围

#include <iostream> #include <vector> using namespace std;const int N = 2e5 + 10;vector<int> e[N]; int cnt;void dfs(int u, int fa, int col) {if (col) cnt ++ ;for (auto v : e[u])if (v != fa)dfs(v, u, col ^ 1); }int main() {int _; cin >> _;while (_ -- ){int n; scanf("%d", &n);cnt = 0;for (int i = 1; i <= n; i ++ ) e[i].clear();for (int i = 0, u ,v; i < n - 1 && scanf("%d%d", &u, &v); i ++ )e[u].push_back(v), e[v].push_back(u);dfs(1, 0, 1);printf("%lld\n", 1ll * cnt + 1ll * cnt * (cnt - 1) / 2);} }

总结

以上是生活随笔为你收集整理的变异蛮牛 树，dfs，二分图染色 牛客白月赛44的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。