Cerinta completa

You are given a tree with N nodes with every node being colored. A color is represented by an integer ranging from 1 to 109. Can you find the number of distinct colors available in a subtree rooted at the node s?

Input Format
The first line contains three space separated integers representing the number of nodes in the tree (N), number of queries to answer (M) and the root of the tree.

In each of the next N-1 lines, there are two space separated integers(a b) representing an edge from node a to Node b and vice-versa.

N lines follow: N+ith line contains the color of the ith node.

M lines follow: Each line containg a single integer s.

Output Format
Output exactly M lines, each line containing the output of the ith query.

Constraints
0 <= M <= 105
1 <= N <= 105
1 <= root <= N
1 <= color of the Node <= 109

Example

Sample Input

4 2 1
1 2
2 4
2 3
10
20
20
30
1
2

Sample Output

3
2

Explanation

Query 1-Subtree rooted at 1 is the entire tree and colors used are 10 20 20 30 , so the answer is 3(10,20 and 30)

Query 2-Subtree rooted at 2 contains color 20 20 30, so the answer is 2(20 and 30)

Limbajul de programare folosit: cpp14

Cod:

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

vector<vi> g;
vector<int> parent;
vi t_ord;

void tree_getorder(int root) {
    int n = g.size();
    parent.assign(n, -1);

    vector<int> stk; stk.push_back(root);
    while(!stk.empty()) {
        int i = stk.back(); stk.pop_back();
        t_ord.push_back(i);
        rep(j, g[i].size()) {
            int c = g[i][j];
            if(parent[c] == -1 && c != root) {
                stk.push_back(c);
            }else {
                parent[i] = c;
            }
        }
    }
}

int ans[100000];
set<int> s[100000];
int color[100000];
int main() {
    int N, M, root;
    scanf("%d%d%d", &N, &M, &root); root --;
    g.assign(N, vi());
    rep(i, N-1) {
        int a, b;
        scanf("%d%d", &a, &b);
        a --, b --;
        g[a].pb(b);
        g[b].pb(a);
    }
    rep(i, N) scanf("%d", &color[i]);
    tree_getorder(root);
    rep(i, N) s[i].clear();
    for(int ordi = N-1; ordi >= 0; ordi --) {
        int v = t_ord[ordi];
        s[v].insert(color[v]);
        ans[v] = s[v].size();
        int u = parent[v];
        if(u == -1) continue;
        if(s[u].size() < s[v].size())
            swap(s[u], s[v]);
        s[u].insert(all(s[v]));
        set<int>().swap(s[v]);
    }
    rep(i, M) {
        int s;
        scanf("%d", &s); s --;
        printf("%d\n", ans[s]);
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464653703

Link challenge: https://www.hackerrank.com/challenges/coloring-tree/problem

Coloring Tree