Tree Troubles

0

0 votes
Medium
Problem

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 :

  • 1n105
  • 1u,vn
  • 0state1
  • 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.

    Time Limit: 1
    Memory Limit: 256
    Source Limit:
    Editor Image

    ?