title: what is the fastest way to get the height after changing the root of the tree?
body: <p>I have a tree with n node, and m queries. For each query, they ask me to find the height of tree from a given node (assumes they choose that node as root).</p>
  
  <p>we will have maximum <code>10^5</code> node, and <code>10^5</code> queries.</p>
  
  <p>it's simple to get height from only one node as root. But for this problem, i don't see any efficient way to solve it.</p>
  
  <p>I have to traverse the tree again and again for each query. It take too much time.</p>
  
  <p>there must be some way that I can just traverse the tree only one from any node as root, and then calculate the height for each query. </p>
  
  <p>So, is there any solution?</p>
  
  <p>here is the problem :</p>
  
  <p>you're given a tree with n vertices, and m queries. For each query, find the heigh of the tree when choosing vertex R as root</p>
  
  <p>First line consists of N, i.e number of vertex. <code>1 &lt;= n &lt;= 10^5</code></p>
  
  <p>Next N-1 lines follow the type U V which denotes there is a path from U to V. <code>0 &lt;= U, V &lt;= n - 1</code></p>
  
  <p>Next line contain m, i.e number of query <code>1 &lt;= m &lt;= 10^5</code></p>
  
  <p>followed by m line, each line contain a vertex R chosen as root.</p>
  
  <p>output the height for each query.</p>
  
  <pre><code>input
  5
  0 1
  0 2
  2 3
  3 4
  5
  0
  1
  2
  3
  4
  output
  3
  4
  2
  3
  4
  </code></pre>