902B - Coloring a Tree - CodeForces Solution


dfs and similar dsu greedy *1200

Please click on ads to support us..

C++ Code:

/* ____                       _  __                     _       _       _       
  |  _ \ _ __ ___ _ __ ___   | |/ /__ _ _ __ ___   __ _| |     | | __ _(_)_ __  
  | |_) | '__/ _ \ '_ ` _ \  | ' // _` | '_ ` _ \ / _` | |  _  | |/ _` | | '_ \ 
  |  __/| | |  __/ | | | | | | . \ (_| | | | | | | (_| | | | |_| | (_| | | | | |
  |_|   |_|  \___|_| |_| |_| |_|\_\__,_|_| |_| |_|\__,_|_|  \___/ \__,_|_|_| |_|
*/                                                                            

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long ull;
typedef long double lld;

#define hell    1000000007
#define PI      3.141592653589793238462
#define INF     1e18
#define vi      vector<ll>
#define pb      push_back
#define ppb     pop_back
#define mii     map<ll,ll>
#define pii     pair<ll,ll>
#define mp      make_pair
#define ff      first
#define ss      second
#define all(x)  (x).begin(), (x).end()

/*____________________________________________________________________________________________________________________________________________________________________________________________________*/
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
// ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
/*____________________________________________________________________________________________________________________________________________________________________________________________________*/

ll dfs(vi adj_list[], ll color[], bool visited[], ll current){
    visited[current] = true;
    ll ans = 0;
    for(auto next_vertex : adj_list[current]){
        if(!visited[next_vertex]){
            if(color[next_vertex] != color[current]){
                ans++;
            }
            ans += dfs(adj_list, color, visited, next_vertex);
        }
    }
    return ans;
}

void solve()
{
    ll n;
    cin >> n;
    vi adj_list[n + 1];
    for(ll i = 2; i <= n; i++){
        ll x;
        cin >> x;
        adj_list[i].pb(x);
        adj_list[x].pb(i);
    }

    ll color[n + 1];
    bool visited[n + 1];
    for(ll i = 1; i <= n; i++){
        cin >> color[i];
        visited[i] = false;
    }

    ll ans = dfs(adj_list, color, visited, 1);
    cout << ans + 1 << endl;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    for(ll i = 0; i < t; i++){
        solve();
    }
    return 0;
}


Comments

Submit
0 Comments
More Questions

1569C - Jury Meeting
108A - Palindromic Times
46A - Ball Game
114A - Cifera
776A - A Serial Killer
25B - Phone numbers
1633C - Kill the Monster
1611A - Make Even
1030B - Vasya and Cornfield
1631A - Min Max Swap
1296B - Food Buying
133A - HQ9+
1650D - Twist the Permutation
1209A - Paint the Numbers
1234A - Equalize Prices Again
1613A - Long Comparison
1624B - Make AP
660B - Seating On Bus
405A - Gravity Flip
499B - Lecture
709A - Juicer
1358C - Celex Update
1466B - Last minute enhancements
450B - Jzzhu and Sequences
1582C - Grandma Capa Knits a Scarf
492A - Vanya and Cubes
217A - Ice Skating
270A - Fancy Fence
181A - Series of Crimes
1638A - Reverse