Gangsters of Treeland

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Treeland is a kingdom consisting of N cities labelled 0, 1, 2, ... N1. There are N1 roads connecting these cities such that each pair of cities is connected by a unique path(forming a tree structure). Needless to say, city 0 is the capital of Treeland. Initially, each city is controlled by a different gangster. The citizens are allowed to move from any city to any of its adjacent city. However, if the two cities are controlled by different gangsters, they need to pay unit cost in order to move. The distance between any pair u, v of cities denoted by dist(u,v) is defined as the minimum cost a person has to pay to go from u to v(or v to u).
Every year, a new gangster emerges in the capital. As always, the gangster will wish to expand his territory. To do so, he will choose a city u, and march with his gangster army from the capital to u(along the tree path). All the cities they encounter(including capital and u) will be forciby occupied by this gangster. Because of this, distance between many cities can potentially change, which makes the people mad. Therefore, they will come to you for help.
Given a city u, they will ask you evaluate
f(u) = avg_{x in subtree rooted at u(including u)} dist(capital, x)
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of cities in Treeland. The next N1 lines contain two spaceseparated integers A_{i}, B_{i} denoting the i^{th} road is between cities A_{i} and .B_{i}.
The next line contains Q, the number of queries. The next Q lines each contain a character t and an integer u .
If t='O', it means a new gangster has marched from capital to u, Occupying all cities along the path.
If t='q', it means you have to report f(u)
Output
Constraints
 1 ≤ T ≤ 15
 1 ≤ N ≤ 100000
 1 ≤ Q ≤ 100000
 The sum of value of N over all test cases will be no more than 200000.
 The sum of value of Q over all test cases will be no more than 200000.
Example
Input: 1 13 0 1 0 2 1 11 1 10 1 9 9 12 2 5 5 8 2 4 2 3 4 6 4 7 7 q 0 O 4 q 6 q 2 O 9 q 9 q 2 Output: 2.0000000000 1.0000000000 0.8571428571 0.5000000000 1.8571428571
Explanation
Initially, distance of each city from capital is equal to the number of edges on the shortest path, because each city is controlled by a different gangster.
Therefore, value of f(0) is (0+1+1+2+2+2+3+2+2+3+2+3+3)/13 = 2.
After performing 'O 4', cost of the edges (0,2) and (2,4) become 0. The cost of all other edges remains same. Therefore, f(6) becomes 1.
Author:  utkarsh_lath 
Editorial  http://discuss.codechef.com/problems/MONOPLOY 
Tags  medium, nov13, utkarsh_lath 
Date Added:  26062013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, CS2, PAS fpc, PAS gpc, GO, NODEJS, HASK, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions