Link to editorial is not added on this problem page.
2 Likes
black_
u+=((B_u) ?1+ ∑white_x : ∑black_x) over all children x of node u
If in the end we need the colour of node u as white we need to first colour the whole subtree of u white otherwise we can just leave the node u untouched and calculate the answer for black_x for all children x of node u and add them to black_u
Please explain this @devendra7700 , @cubefreak777 its not clear to me, would be a great help.
.
3 Likes
In this case we are trying to calculate the answer for minimum number of operations needed for subtree of u to look exactly the same as needed in the final tree assuming that the whole subtree was first painted black by some operation. Now since every node is black in the subtree of u, if we need u to be white in the final tree we need to first colour the subtree of u white using an operation and then add the answer for all child nodes assuming they are all painted white. If we need u to be black we can just skip any operation on u as it is already black and add the answer for children of u assuming they are all painted black.
3 Likes
Now its crystal clear thanks a lot bro 
Could someone please correct me where my approach will fail.
My approach:-
For all the nodes where a[u] != b[u] we need to change the color once, except if this node belongs to a subtree where all the nodes are to be changed to the same color, and the head of this subtree also has the same b[i].
Try this:
1
4
0 1 1 1
0 0 1 0
2 1
1 4
3 4
Correct output is 2
1 Like
Try this:
1
5
1 0 0 0 0
1 1 0 1 1
2 1
1 4
4 3
3 5
Correct output is 3
1 Like
Here, if the Bu = 1, which should mean the final state is black, So shouldn’t we be summing the answer for when all children are turned black. Why are we doing “1+∑whitex” if Bu = 1.
P.S : Sorry, if am being silly. I am really confused.
1 Like
Thanks, updated
1 Like
my solution
#include <bits/stdc++.h>
#define ull unsigned long long int
#define ui unsigned int
#define ll long long int
#define f(i, n) for (ll i = 0; i < n; i++)
const ll m = 10e9 + 7;
// const ll N = 10e5 + 5;
using namespace std;
ll binpow(ll a, ll b, ll m)
{
a %= m;
ll res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
void dfs(vector edges[], vector &visited, vector &dp, vector &dpw, vector &dpb, int curr, vector &arr1, vector &arr2)
{
if (visited[curr])
return;
visited[curr] = true;
int n = edges[curr].size();
for (int i = 0; i < n; i++)
{
dfs(edges, visited, dp, dpw, dpb, edges[curr][i], arr1, arr2);
}
ll black = 0;
ll white = 0;
f(i, n) black += dpb[edges[curr][i]];
f(i, n) white += dpw[edges[curr][i]];
if (arr2[curr] == 1)
{
dpb[curr] += black;
dpw[curr] += 1;
dpw[curr] += black;
}
else
{
dpb[curr] += 1;
dpb[curr] += white;
dpw[curr] += white;
}
if (arr1[curr] == arr2[curr])
{
f(i, n)
dp[curr] += dp[edges[curr][i]];
dp[curr] = min(dp[curr], 1 + min(dpw[curr], dpb[curr]));
}
else if (arr2[curr] == 1)
{
dp[curr] += 1 + black;
}
else
{
dp[curr] += 1 + white;
}
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
vector<ll> arr1(n), arr2(n);
vector<ll> edges[n];
f(i, n) cin >> arr1[i];
f(i, n) cin >> arr2[i];
f(i, n - 1)
{
int u, v;
cin >> u >> v;
u--;
v--;
edges[u].push_back(v);
edges[v].push_back(u);
}
vector<ll> dp(n, 0);
vector<ll> dpw(n, 0);
vector<ll> dpb(n, 0);
vector<bool> visited(n, 0);
dfs(edges, visited, dp, dpw, dpb, 0, arr1, arr2);
cout << dp[0] << '\n';
}
return 0;
}
https://www.codechef.com/viewsolution/66028146
I followed editorial,
still getting TLE.
Can anyone help?
void dfs(int v, vi adj[],vl & black, vl & white, vl & none, vl & vis, int A[],int B[]){
vis[v]=1;
ll sumbx=0;
ll sumwx=0;
ll sumnx=0;
ll summinch=0;
for(auto i : adj[v]){
if(vis[i]==0){
dfs(i,adj,black,white,none,vis,A,B);
sumbx+=black[i];
sumwx+=white[i];
sumnx+=none[i];
summinch+=min({1+black[i],1+white[i],none[i]});
}
}
none[v]=(A[v]!=B[v])? (int)1e9 : summinch; // if not equal then inf since no operation , else min of each child added.
black[v]= (B[v]==0)? 1+sumwx : sumbx ;//if reqd to be white then 1 + sum of all child white, else sum of all child black;
white[v]= (B[v]==1)? 1 +sumbx : sumwx ;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int A[n],B[n];
for (int i = 0; i < n; i++)
{
cin>>A[i];
}
for (int i = 0; i < n; i++)
{
cin>>B[i];
}
vi adj[n];
for (int i = 0; i < n-1; i++)
{
int x,y;
cin>>x>>y; x--;y--;
adj[x].pb(y);
adj[y].pb(x);
}
vl black(n,0);
vl white(n,0);
vl none(n,0);
vl vis(n,0);
dfs(0,adj,black,white, none,vis,A,B);
cout<<min({none[0],1+black[0],1+white[0]})<<"\n";
}
return 0;
}
Simple solution easy to understand.
1
5
0 0 0 1 0
0 1 0 1 1
2 4
3 1
1 4
4 5
Correct Output is 1
Thanks a lot bro 
Here I tried an approach of creating actual tree which makes this problem bit easier to solve to 
#include<bits/stdc++.h>
using namespace std;
#define lim 300001
#define ll long long int
#define a(i,s,e) for(ll i=s;i<e;i+=1)
#define ra(i,s,e) for(ll i=s-1;i>=e;i-=1)
#define pb push_back
//this dp table will store all the possible states than can happen in the tree.
// at max this table will get filled after 3*n assignments hence the complexity of the algo will be O(n).
int dp[lim][3];
// defining the class for the node of the tree.
class node{
public:
int val;
bool empty = true;
vector<node*> child;
node(int x){
val = x;
}
};
// create a tree of actual nodes rather than the adjacency list to get rid of this visited array.
node* create_tree(vector<vector<ll>>&adj,int u,vector<bool>&vis){
vis[u] = true;
node* ans = new node(u);
for(auto x: adj[u]){
if(!vis[x]){
ans->empty = false;
ans->child.push_back(create_tree(adj,x,vis));
}
}
return ans;
}
// st is the state-> 0: black , 1: white , 2: none , black and white correspond to that subtree to which root belongs to be completely colour.
// none means the original config of the tree is maintained.
int solve(int st,node* root,vector<int>&a,vector<int>&b){
int c = root->val;
// if already calculated then simply return the answer.
if(dp[c][st]!=-1) return dp[c][st];
else{
if(st==2){
int ans1 = 0;// this stores the result when we do not perform any operation on current node.
int ans2 = 1;// this stores the result when we perform oper. which may help in subtrees of its children.
if(a[c]==b[c]){
for(auto x: root->child){
ans1 += solve(2,x,a,b);
ans2 += solve(a[c],x,a,b);
}
}
else{
ans1 = lim;// if a[curr]!=b[curr] then we cannot omit performing any oper. hence this makes ans1 out of the picture. only ans2 is returned.
for(auto x: root->child){
ans2+= (solve(b[c],x,a,b));
}
}
return dp[c][st] = min(ans1,ans2);// compare which result requires minimum operations.
}
// here st !=2 this means whole subtree is painted with colour equal to value of st.
else{
int ans = 0;
if(b[c]==st){
// if the required colour is equal to the colour of subtree then it is useless to perform any operation on this node
// bcz after that also the successors will be of the same colour as before.
for(auto x: root->child){
ans+= solve(st,x,a,b);
}
}
else{
// if required colour is opposite to colour of subtree, we must perform an operation and all the subtree of this node will be coloured
// as b[c].
ans++;
for(auto x: root->child){
ans+= solve(b[c],x,a,b);
}
}
return dp[c][st] = ans;// store ans in dp table.
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
vector<int> ar(n),br(n);
vector<vector<ll>> adj(n);
vector<bool> vis(n);
a(i,0,n){
cin>>ar[i];
}
a(i,0,n){
cin>>br[i];
}
// changed to 0 based indexing.
a(i,0,n-1){
ll a,b;
cin>>a>>b;
a--;b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
a(i,0,n){
a(j,0,3){
dp[i][j] = -1;
}
}
// tree rooted at 0.
node* root = create_tree(adj,0,vis);
// starting from the root we can either calculate result from original config or,(ans1);
// can calculate ans if whole tree is painted br[0] but since this node has no parent we perform 1 operation on this node itself(ans2);
int ans1 = solve(2,root,ar,br);
int ans2 = 1+solve(br[0],root,ar,br);
cout<<min(ans1,ans2)<<endl;
}
return 0;
}