题目链接<–点这里

这段时间写了好多dfs,感觉这题比较有挑战?看了眼题解才想到思路,然后代码实现感觉也不太简单……

Coloring a Tree

题目链接<–点这里

题目意思: 给你n个点,代表这一棵树有n个节点。第二行内容是建树的关系,从第二个节点开始的节点和父节点(上一个节点)相连,

例如:1 2 2 1 5

代表:节点2和节点1相连,节点3和节点2相连,节点4和节点2相连,节点5和节点1相连,节点6和节点5相连。

第三行内容是需要将各个点涂成的颜色,给这个树涂色,有这么一条原则就是给某一节点涂色,以其为根节点的子树也将变为相应的颜色,问你最终需要最少需要涂多少次颜色就可以满足题目要求。

解题思路:我们可以这样来思考,因为最后需要使所有的点都涂成要求的颜色,一定是按照从根节点到叶子节点遍历的涂色,但所有的点都遍历会造成浪费,我们只需要找出需要涂的点即可。

那么哪些点需要涂呢?我们发现只有那些最后要求的其父亲节点和本身不同色的需要涂色,因为需要向下改变自身颜色,那么只需要统计这样点的个数即可。

一开始我苦思冥想怎么建树,把层次关系可以弄明白。但是后来发现完全不需要,只需要记录每个节点的父节点是谁就好了。我采用的是结构体排序,每对父子节点都存两遍,改变先后顺序。之后从根节点开始,把所有存在父子关系的点都加入节点i的队列。再从根节点的队列开始遍历,把每个没有更新父节点的节点当成当前节点的子节点。

sum的初值是1,因为根节点肯定需要涂色。然后从2到n扫一遍,当前节点与当前节点的父节点是否属于一种颜色,不相同则sum++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

struct Tree
{
int l,r;
}t[20005];

bool cmp(Tree a,Tree b)
{
if(a.l==b.l)
return a.r<b.r;
return a.l<b.l;
}

int father[10005];
int color[10005];
queue<int>q[100005];

int main()
{
ios::sync_with_stdio(false);
int n,ans=0;
cin>>n;
for(int i=2;i<=n;i++)
{
int y;
cin>>y;
t[ans].l=i;t[ans++].r=y;
t[ans].l=y;t[ans++].r=i;
}
for(int i=1;i<=n;i++)
{
cin>>color[i];
father[i]=-1;
}
//cout<<1<<endl;
sort(t,t+ans,cmp);
for(int i=0;i<ans;i++)
{
q[t[i].l].push(t[i].r);
}
for(int i=1;i<=n;i++)
{
while(!q[i].empty())
{
if(father[q[i].front()]==-1&&q[i].front()!=1)
{
father[q[i].front()]=i;
}
q[i].pop();
}
}
int sum=1;
for(int i=2;i<=n;i++)
{
if(color[i]!=color[father[i]])
sum++;
}
cout<<sum<<endl;
return 0;
}

最后更新: 2019年09月26日 20:26

原始链接: http://yisin.top/2019/09/26/Coloring-a-Tree/

× 请我吃糖~
打赏二维码