构造类问题往往都是由特殊到简单而对于树形结构最特别的就是叶子
#include <bits/stdc++.h>
using namespace std;
int n, tot = 0;
int head[100010];
struct ty
{
int t, next;
}edg
展开全文
叶子节点之与父亲有边相连，所以叶子节点必然与父亲同色。 而父亲节点已经和叶子节点同色，所以叶子节点必然与爷爷节点异色。 爷爷的颜色确定后，如果爷爷还与一条边相连，那么标记爷爷的相邻点颜色也确定。对于任何一条路径，可以这样递归上去。 所以统计同色（友）信息然后再跑一边DFS染色即可 #include
展开全文
思路 由每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点可得，如果叶子结点为一种颜色时，它的周围只有其父亲结点，所以父亲结点和它同色。 根据上述我们可以进行dfs，从下到上两两配对，存在一个没有与之配对的结点说明不存在此解 配对完成后在进行一遍dfs经行染色，如果是匹配的染同一颜色，
展开全文
import java.util.*;
public class Main {
private static class Node{
List<Node> neighbor = new ArrayList<>();
Node pair
展开全文
解题思路
核心思想：
使用 数组标记配对关系： 表示节点 和 需要染成相同颜色
通过两次DFS完成配对和染色
第一次DFS (dfs1)：确定配对关系
从根节点开始，自底向上处理
对于叶子节点或未配对的节点：
如果其父节点已配对，则无解
否则，将该节点与其父节点配对（赋予相同的
展开全文
题意 给一棵树，把他染成红蓝两种颜色。要求：每个点周围有且仅有有一个点和自己颜色相同不存在输出-1 分析 首先如果n是奇数肯定不存在，接着考虑其他情况，先说jie'l。如果存在某一个点，他的 子树的节点数为奇数，这样的子树个数大于1个的话，则无解。 先从叶子节点考虑，因为叶节点只与父节点相连，所以父
展开全文
21年基础训练营1C红与蓝（图论视角） 近来由于进行蓝桥杯训练，开始复盘总结自己以前做过的搜索题目。由于前几天复习了图论，发现这个题目有一些图论的味道，so 因此记录一下心得。link 题目大体描述 给定一个无根树，请你对使用两种颜色对之染色。使得蓝色周围有且只有一个蓝色，红色周围有且只有一个红色，
展开全文
题目的主要信息：
一棵无向树，给每个顶点染成红色或蓝色
每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点
无法完成染色输出-1，完成染色输出每个结点的颜色
具体做法：
首先叶子结点因为只与父亲结点相连，所以叶子结点与父亲结点同色，因此我们可以利用dfs从根节点开始递归遍历树，从叶子结点
展开全文
红和蓝
难度：4星
可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：
若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。
若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
