小红拿到了一棵树，每个节点上有一个字符，每个节点上的字符为’d’、’p’、’?’这三种。 现在请你将所有’?’字符变成’d’或者’p’字符，需要满足任意两个相邻节点的字符不同。你能帮帮她吗？
区块链毕设网qklbishe.com为您提供问题的解答
小红拿到了一棵树，每个节点上有一个字符，每个节点上的字符为’d’、’p’、’?’这三种。
现在请你将所有’?’字符变成’d’或者’p’字符，需要满足任意两个相邻节点的字符不同。你能帮帮她吗？
import sys from collections import defaultdict def check(node, adj, data_list): for v in adj[node]: if data_list[v] == '?': continue if data_list[v] == data_list[node]: return False return True n = int(input()) data_list = list(input()) adj = defaultdict(list) for _ in range(n - 1): u, v = map(int, input().split()) adj[u - 1].append(v - 1) adj[v - 1].append(u - 1) queue = [] for i in range(n): if data_list[i] == '?': continue if check(i, adj, data_list) == False: print(-1) exit() else: queue.append(i) if len(queue) == 0: queue.append(0) data_list[0] = 'd' while len(queue) > 0: tmp_len = len(queue) for i in range(tmp_len): node = queue[i] for v in adj[node]: if data_list[v] != '?': continue if data_list[node] == 'd': data_list[v] = 'p' else: data_list[v] = 'd' queue.append(v) queue = queue[tmp_len:] for node in queue: if not check(node, adj, data_list): print(-1) exit() print(''.join(data_list))
33:41
以上就是关于问题小红拿到了一棵树，每个节点上有一个字符，每个节点上的字符为’d’、’p’、’?’这三种。
现在请你将所有’?’字符变成’d’或者’p’字符，需要满足任意两个相邻节点的字符不同。你能帮帮她吗？的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}