首页 > 试题广场 >

小美的树上染色

[编程题]小美的树上染色

热度指数：2396 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

		小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。
	
		小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。
	
		小美想知道，自己最多可以染红多少个节点？

输入描述:

第一行输入一个正整数，代表节点的数量。
第二行输入个正整数，代表每个节点的权值。
接下来的行，每行输入两个正整数，代表节点和节点有一条边连接。

输出描述:

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

示例1

输入

输出

说明

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

算法知识视频讲解

Java

怪_兽

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [][]nums = new int[n][2];
for (int i = 0; i < n; i++) {//赋节点权值
nums[i][0] = in.nextInt();//节点值
nums[i][1] = 0;//0白色，1红***r /> }
int [][]conn = new int[n - 1][2];//创建节点关系二维数组
for (int i = 0; i < n - 1;i++) { //总共n-1行节点关系 0 - n-2 （n-2+1=n-1）
conn[i][0] = in.nextInt();
conn[i][1] = in.nextInt();
conn[i][0] -= 1;//对应索引要减一
conn[i][1] -= 1;
}
int sum = 0; //红色节点个数
int i = n - 1;
while (--i >= 0) {
if (nums[conn[i][0]][1] == 0 && nums[conn[i][1]][1] == 0) {
if (Math.pow((int)Math.sqrt(nums[conn[i][0]][0] * nums[conn[i][1]][0]),
2) == (nums[conn[i][0]][0] * nums[conn[i][1]][0])) {
nums[conn[i][0]][1] = 1; //节点值设为1，红***r /> nums[conn[i][1]][1] = 1;
sum += 2;
}
}
}
System.out.println(sum);
}
}

发表于 2023-10-05 22:34:48 回复(2)