1
5
0 0 0 1 0
0 1 0 1 1
2 4
3 1
1 4
4 5
Correct Output is 1
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;
}