题目链接<–点这里

这段时间写了好多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++。

#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;
}

小仙女