首页 > 试题广场 >

小美的树上染色

[编程题]小美的树上染色
  • 热度指数：362 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。
小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。
小美想知道，自己最多可以染红多少个节点？

输入描述:
第一行输入一个正整数n，代表节点的数量。
第二行输入n个正整数a_i，代表每个节点的权值。
接下来的n-1行，每行输入两个正整数u,v，代表节点u和节点v有一条边连接。
1\leq n \leq 10^5
1\leq a_i \leq 10^9
1\leq u,v \leq n


输出描述:
输出一个整数，表示最多可以染红的节点数量。
示例1

输入

3
3 3 12
1 2
2 3

输出

2

说明

可以染红第二个和第三个节点。
请注意，此时不能再染红第一个和第二个节点，因为第二个节点已经被染红。
因此，最多染红 2 个节点。

算法知识视频讲解
开通博客
头像 Mag1c0nch
发表于 2024-11-28 22:21:51
我们可以直接dfs这棵树，在回溯的时候判断，如果当前节点和其父亲是满足条件的且都是白色节点，那么一定可以将其染色，因为这时一定代表着当前节点 u 不存在儿子 v ，使得 u v 满足条件，不然 u 已经是红色了，这样贪心的染色一定可以染出最大答案 #include <bits/stdc++.h 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 君鸿
发表于 2024-12-25 11:19:43
整体思路先定义一个概念【叶子】节点：该节点为白色节点，有且只有一个相邻节点可以一起涂成红色。若某个白色节点A存在多个相邻节点，但其中只有一个相邻的白色节点，满足双方权值的乘积是完全平方数，那么节点A也是叶子节点。本题有一个关键的说明，也就是第一句话：小美拿到了一棵树。既然是树，那么就不存在环。因此根 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 栗悟饭与龟功気波
发表于 2024-11-29 00:05:18
小美的树上染色 这是题面 思路 题目的限制条件有两个 节点需要是相邻的 都还没被访问过并且乘积是一个完全平方数 然后求最多能访问多少个节点 如果从根开始考虑的话，可能不是很好想，因为跟可能有很多儿子，和哪个儿子结合呢？好像不好想 那我们可以试着从叶子节点开始考虑，因为叶子节点能够结合的只 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Ke_scholar
发表于 2024-11-29 19:47:22
提供一种DP的思路；dp[i][0/1]表示第i个结点染色不染色/染色的最大的染色数量。那么对于dp[i][0]来说就是它的子节点的染色最大树量的和，dp[i][1]则需要再来一轮循环，统计某个子节点与父节点一起染色的最大值。 #include <bits/stdc++.h> usin 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 努力变强2
发表于 2024-11-28 21:15:46
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll>PII; const int N = 1e5 + 10; const int MOD = 9982 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
1条回答 68浏览

热门推荐

相关试题

小美的树上染色

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号