// Arup Guha
// 11/10/2025
// 2025 SER D1/D2 Problem D: GUID Generator
// Coded for COP 3502 to illustrate use of trie and recursion together!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 2000
#define NUMLET 16

typedef struct list {
    int* arr;
    int size;
    int capacity;
} list;

typedef struct trie {
    int isWord;
    struct trie* next[NUMLET];
} trie;

void init(list* ptrList);
void add(list* ptrList, int val);
trie* makeNewNode(int word);
int count(trie* root);
void go(int u, int* used, int n, trie* root, list* graph, char letters[]);
int f(char c);

int main() {

    int n;
    scanf("%d", &n);

    // Allocates n lists.
    list* graph = calloc(n, sizeof(list));
    for (int i=0; i<n; i++)
        init(&graph[i]);

    // Read in node labels.
    char letters[MAX+1];
    scanf("%s", letters);

    // Read in edges/connections.
    for (int i=0; i<n-1; i++) {

        // Read in this edge. Make 0 based.
        int u, v;
        scanf("%d%d", &u, &v);
        u--; v--;
        add(&graph[u], v);
        add(&graph[v], u);
    }

    // Root of my trie.
    trie* mine = makeNewNode(0);

    // i is the node I am starting from.
    for (int i=0; i<n; i++) {

        // Used array.
        int* used = calloc(n, sizeof(int));

        // Make this node if we need to.
        if (mine->next[f(letters[i])] == NULL)
            mine->next[f(letters[i])] = makeNewNode(1);

        // Start our process to search through the graph from i.
        go(i, used, n, mine->next[f(letters[i])], graph, letters);
    }

    // Ta da!
    printf("%d\n", count(mine));
    return 0;
}

// Returns the number of words in the trie pointed to by root.
int count(trie* root) {

    // Avoid null ptr.
    if (root == NULL) return 0;

    // Add root.
    int res = root->isWord;

    // Then all subtrees.
    for (int i=0; i<NUMLET; i++)
        res += count(root->next[i]);
    return res;
}

// Recursively marks each node we can reach from u, building nodes in the trie
// pointed to by root as needed.
void go(int u, int* used, int n, trie* root, list* graph, char letters[]) {

    // Mark here.
    used[u] = 1;

    // Go to each neighbor of u.
    for (int i=0; i<graph[u].size; i++) {

        // Where I can travel from u.
        int v = graph[u].arr[i];

        // Don't go here, been there before.
        if (used[v]) continue;

        // The letter I care about.
        int letIdx = f(letters[v]);

        // Make this node before we recurse.
        if (root->next[letIdx] == NULL)
            root->next[letIdx] = makeNewNode(1);

        // Now continue our search from here.
        go(v, used, n, root->next[letIdx], graph, letters);
    }
}

// Returns a 0 to 15 value corresponding to the hex char.
int f(char c) {
    if (c >= '0' && c <= '9')
        return c - '0';
    return c - 'a' + 10;
}

// Initialize list pointed to by ptrList.
void init(list* ptrList) {
    ptrList->arr = calloc(10, sizeof(int));
    ptrList->size = 0;
    ptrList->capacity = 10;
}

// Adds val to list pointed to by ptrList.
void add(list* ptrList, int val) {

    // Double size if necessary.
    if (ptrList->size == ptrList->capacity) {
        ptrList->arr = realloc(ptrList->arr, 2*ptrList->size*sizeof(int));
        ptrList->capacity *= 2;
    }

    // Add value.
    ptrList->arr[ptrList->size] = val;
    ptrList->size++;
}

// Returns a new root node for a trie.
trie* makeNewNode(int word) {
    trie* tmp = malloc(sizeof(trie));
    tmp->isWord = word;
    for (int i=0; i<NUMLET; i++)
        tmp->next[i] = NULL;
    return tmp;
}