标题:想问一下这个题的求解思路
只看楼主
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
结帖率:92%
已结贴  问题点数:20 回复次数:1 
想问一下这个题的求解思路
题目描述
现假设实验室总共要制造n瓶试剂,每瓶试剂有各自的颜色,经过试验,发现这n瓶试剂构成了树形的关系,若某瓶试剂经过反应变成了某种颜色,则其子树中的各瓶试剂也变成了该颜色。问最少要多少次反应才能将每瓶试剂变成对应的颜色,且1号节点为根节点。

输入
多组数据
第一行:数据组数 T(1<=T<=100)
第二行:一个整数n (2 ≤ n ≤ 1e4) 代表有多少瓶试剂
第三行:n-1 个整数p2, p3, ..., pn (1 ≤ pi < i)代表在试剂i和pi之间有一条边。
第四行:n 个整数c1, c2, ..., cn (0 ≤ ci ≤ n),表示试剂i应该变成的颜色。

输出
每组数据输出一行,一个整数,代表最少的反应次数。

样例输入
2
6
1 2 2 1 5
2 1 1 1 1 1
7
1 1 2 3 1 4
3 3 1 1 1 2 3
样例输出
3
5
搜索更多相关主题的帖子: 思路 颜色 数据 整数 代表 
2018-05-26 09:00
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:20 
                 1
           2           5
        3    4           6

这个是案例1的树嘛~
3步就是

把1染2
把2染1
把5染1

就想到第一步先染根结点

用队列进行层次遍历,找结点和着色要求不同的来看看

PS:这题技术细节上有点难度,要把森林转化成二叉树才好处理~



[此贴子已经被作者于2018-5-26 09:45编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-26 09:36



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-487290-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.125275 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved