//heavy-light decomposition style .
//http://codeforces.com/blog/entry/44351

int cnt[maxn];

bool big[maxn];

void add(int v, int p, int x){

    cnt[ col[v] ] += x;

    for(auto u: g[v])

        if(u != p && !big[u])

            add(u, v, x)

}

void dfs(int v, int p, bool keep){

    int mx = -, bigChild = -;

    for(auto u : g[v])

       if(u != p && sz[u] > mx)

          mx = sz[u], bigChild = u;

    for(auto u : g[v])

        if(u != p && u != bigChild)

            dfs(u, v, );  // run a dfs on small childs and clear them from cnt

    if(bigChild != -)

        dfs(bigChild, v, ), big[bigChild] = ;  // bigChild marked as big and not cleared from cnt

    add(v, p, );

    //now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.

    if(bigChild != -)

        big[bigChild] = ;

    if(keep == )

        add(v, p, -);

}