Tree Troubles
Practice
0 (0 votes)
Medium
Problem
72% Success 25 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code
Given a tree T with n nodes and n - 1 edges rooted at node 1. Each nodes can be of two types namely "Sad" and "Happy". You can perform 2 operations each with a unit cost :
- Flip the state of the node from Happy to sad or Sad to Happy.
- Flip the state of all the nodes in subtree of Node x (including node x itself).
Given the current and final state of tree. Find the minimum cost required for the transformation.
Constraints :
Input :
- First line contains n, number of nodes.
- Next n - 1 line contains 2 integers u and v each denoting edge between node u and v.
- Next line contains n integers denoting the current state of Tree.
- Next line contains n integers denoting the final state of Tree.
Note : "0" denotes "Sad" State and "1" denotes "Happy" State
Output :
Print one line containing the minimum cost as described above.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
10 votes
Tags:
Dynamic ProgrammingAlgorithmsTrees
Points:30
3 votes
Tags:
TreeDynamic ProgrammingAlgorithmsMedium
Points:30
6 votes
Tags:
Dynamic ProgrammingAlgorithmsTrees
Editorial
No editorial available for this problem.