codeforces902B. Coloring a Tree

B. Coloring a Tree

题目链接:

https://codeforces.com/contest/902/problem/B

题意：给你一颗树，原先是没有颜色的，需要你给树填色成指定的样子，每次填色的话，子树会和根节点变成同一种颜色，问需要多少次填色

题解：前向星建树，从每个父节点便利，如果父节点的颜色和子节点不一样就ans++吗，最后记得把第一次操作（根节点涂色的次数给记上

代码如下：

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define fuck(x) cout<<"["<<x<<"]";

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int maxn = 3e5+;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9+;

int cnt;

int head[maxn],nxt[maxn],to[maxn];

int color[maxn];

int ans;

void add(int x,int y){

    to[cnt]=y;

    nxt[cnt]=head[x];

    head[x]=cnt++;

}

int main(){

#ifndef ONLINE_JUDGE

    FIN

#endif

    int n,x;

    cnt=;

    memset(head,-,sizeof(head));

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        scanf("%d",&x);

        add(x,i);

    }//前向星连边

    for(int i=;i<=n;i++){

        scanf("%d",&color[i]);

    }

    for(int i=;i<=n;i++){

        for(int j=head[i];j!=-;j=nxt[j]){

            //如果父节点和子树的节点不一样就操作一次

            if(color[i]!=color[to[j]]) ans++;

        }

    }

    cout<<ans+<<endl; //根节点的第一次操作算进去

}

巴特西

codeforces902B. Coloring a Tree

最新文章

热门文章