/*
* [Ctsc2010]珠宝商.cpp
*
* Created on: 2011-4-20
* Author: user
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <climits>
#include <cstring>
#include <vector>
#include <cctype>
#include <cassert>
#include <map>
#define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
using namespace std;
const int MAX_N_VERTEXS = 50000 + 10;
const int MAX_L_PAT = 50000 + 10;
const int MAX_LOG = 20;
const int MAX_NLOGN = MAX_N_VERTEXS * MAX_LOG;
const int MAX_N_ALPHA = 26;
int nVertexs;
int patLen;
char pat[MAX_L_PAT];
struct Vertex;
struct Edge {
Edge*prev, *next, *op;
Vertex*dst;
void reSet() {
prev->next = this;
next->prev = this;
}
void erase() {
prev->next = next;
next->prev = prev;
}
Edge(Vertex*_dst, Edge*_prev, Edge*_next) :
dst(_dst), prev(_prev), next(_next) {
reSet();
}
Edge() {
prev = next = 0;
dst = 0;
}
};
struct Trie {
Trie*ch[MAX_N_ALPHA];
Trie*fail;
Trie() {
memset(ch, 0, sizeof ch);
}
int begin, end;
int depth;
Trie*fail2k[MAX_LOG];
Trie*go(int what) {
Trie*&c = ch[what];
if (c == 0)
c = new Trie;
return c;
}
};
struct Vertex {
Edge*begin, *end;
char ch;
Vertex*father;
int size;
Trie*where;
int branch;
bool visited;
Vertex() {
begin = new Edge;
end = new Edge;
begin->next = end;
end->prev = begin;
}
};
Vertex vertexs[MAX_N_VERTEXS];
void addEdge(Vertex*u, Vertex*v) {
Edge*uv = new Edge(v, u->begin, u->begin->next);
Edge*vu = new Edge(u, v->begin, v->begin->next);
uv->op = vu;
vu->op = uv;
}
void readInput() {
scanf("%d%d", &nVertexs, &patLen);
for (int i = 0; i < nVertexs - 1; ++i) {
int a, b;
scanf("%d%d", &a, &b);
Vertex*u = vertexs + --a, *v = vertexs + --b;
addEdge(u, v);
}
for (int i = 0; i < nVertexs; ++i) {
char ch;
while (ch = getchar(), !isalpha(ch))
;
vertexs[i].ch = ch;
}
scanf(" ");
scanf("%s", pat);
}
int dfsCur;
void dfs(Trie* t, int _depth) {
if (!t)
return;
t->depth = _depth;
t->begin = dfsCur++;
for (int i = 0; i < MAX_N_ALPHA; ++i) {
dfs(t->ch[i], t->depth + 1);
}
t->end = dfsCur - 1;
}
Vertex*que[MAX_N_VERTEXS];
int qh, qt;
void doBFS(Vertex*root) {
qh = qt = 0;
que[qt++] = root;
root->father = 0;
for (; qh < qt;) {
Vertex*u = que[qh++];
for (Edge*e = u->begin->next; e != u->end; e = e->next) {
Vertex*v = e->dst;
if (v == u->father)
continue;
que[qt++] = v;
v->father = u;
}
}
}
Vertex* findSplitVertex(Vertex*root) {
doBFS(root);
for (int i = qt - 1; i >= 0; --i) {
Vertex*u = que[i];
u->size = 1;
for (Edge*e = u->begin->next; e != u->end; e = e->next) {
Vertex*v = e->dst;
if (v == u->father)
continue;
u->size += v->size;
}
}
int bestOpt = INT_MAX;
Vertex*best;
for (int i = 0; i < qt; ++i) {
Vertex*u = que[i];
int opt = root->size - u->size;
for (Edge*e = u->begin->next; e != u->end; e = e->next) {
Vertex*v = e->dst;
if (v == u->father)
continue;
opt = max(opt, v->size);
}
if (opt < bestOpt) {
bestOpt = opt;
best = u;
}
}
return best;
}
const int MAX_N_SPLITS = MAX_N_VERTEXS * 2;
Trie*trieRoot = new Trie;
struct Split {
vector<Trie*>* trieByBranch;
int nBranch;
void init(int nBranch) {
trieByBranch = new vector<Trie*> [nBranch];
this->nBranch = nBranch;
}
void add(int branch, Trie*t) {
trieByBranch[branch].push_back(t);
}
};
Split splits[MAX_N_SPLITS];
int splitsCur = 0;
void buildSplit(Vertex*root, Split&split) {
root->where = trieRoot->go(root->ch - 'a');
doBFS(root);
int curBranch = 0;
for (Edge*e = root->begin->next; e != root->end; e = e->next) {
e->dst->branch = curBranch++;
}
root->branch = curBranch++;
split.init(curBranch);
for (int i = 1; i < qt; ++i) {
Vertex*u = que[i];
u->where = u->father->where->go(u->ch - 'a');
if (u->father != root) {
u->branch = u->father->branch;
}
}
for (int i = 0; i < qt; ++i) {
split.add(que[i]->branch, que[i]->where);
}
}
void doTreeSplit(Vertex*root) {
int id = splitsCur++;
root = findSplitVertex(root);
buildSplit(root, splits[id]);
for (Edge*e = root->begin->next; e != root->end; e = e->next) {
e->erase();
e->op->erase();
doTreeSplit(e->dst);
}
}
void getDfsOrd() {
dfsCur = 0;
dfs(trieRoot, 0);
}
struct Point {
int x, y;
int val;
Point() {
val = 0;
}
Point(int _x, int _y) :
x(_x), y(_y) {
val = 0;
}
bool operator<(const Point&p) const {
return x < p.x;
}
};
bool cmpPointPtrByY(Point*a, Point*b) {
return a->y < b->y;
}
struct DataStruct {
static const int MAX_N_POINTS = MAX_NLOGN;
static const int MAX_SQRT_N_POINTS = 1000 + 10;
struct Block {
int sum[MAX_SQRT_N_POINTS];
Point*points[MAX_SQRT_N_POINTS];
int n;
int addAll;
int L, R;
void set(int _L) {
n = 0;
L = _L;
}
void addPoint(Point*me) {
points[n++] = me;
}
void start() {
R = L + n - 1;
sort(points, points + n, cmpPointPtrByY);
memset(sum, 0, sizeof sum);
}
void applyAdd(int add) {
addAll += add;
}
void relax() {
if (!addAll)
return;
for (int i = 0; i < n; ++i) {
points[i]->val += addAll;
}
addAll = 0;
}
void rebuild() {
sum[0] = 0;
for (int i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + points[i]->val;
}
}
int ask(int ly, int ry) {
static Point*tmp = new Point;
tmp->y = ly;
int atL = lower_bound(points, points + n, tmp, cmpPointPtrByY)
- points;
tmp->y = ry;
int atR = upper_bound(points, points + n, tmp, cmpPointPtrByY)
- points - 1;
int cnt = atR - atL + 1;
return sum[atR + 1] - sum[atL] + cnt * addAll;
}
};
Point points[MAX_N_POINTS];
int nPoints;
Block blocks[MAX_SQRT_N_POINTS];
int nBlocks;
void clear() {
nPoints = 0;
}
void addPoint(int x, int y) {
points[nPoints++] = Point(x, y);
}
void start() {
sort(points, points + nPoints);
nBlocks = 0;
while (nBlocks * nBlocks < nPoints)
++nBlocks;
for (int i = 0; i < nBlocks; ++i) {
blocks[i].set(i * nBlocks);
}
for (int i = 0; i < nPoints; ++i) {
blocks[i / nBlocks].addPoint(points + i);
}
for (int i = 0; i < nBlocks; ++i) {
blocks[i].start();
}
}
void doit(int lx, int rx, int d) {
int at = lx / nBlocks;
blocks[at].relax();
for (int i = lx; i <= rx; ++i) {
points[i].val += d;
}
blocks[at].rebuild();
}
void change(int lx, int rx, int d) {
lx = lower_bound(points, points + nPoints, Point(lx, -1)) - points;
rx = upper_bound(points, points + nPoints, Point(rx, -1)) - points - 1;
if (lx > rx)
return;
int atL = lx / nBlocks;
int atR = rx / nBlocks;
if (atL == atR) {
doit(lx, rx, d);
return;
}
doit(lx, blocks[atL].R, d);
doit(blocks[atR].L, rx, d);
++atL;
--atR;
for (int i = atL; i <= atR; ++i) {
blocks[i].applyAdd(d);
}
}
int ask(int ly, int ry) {
int ret = 0;
for (int i = 0; i < nBlocks; ++i) {
ret += blocks[i].ask(ly, ry);
}
return ret;
}
};
DataStruct dataStrcut;
void calcFail() {
static Trie*que[MAX_NLOGN];
int qh = 0, qt = 0;
que[qt++] = trieRoot;
trieRoot->fail = 0;
while (qh < qt) {
Trie*u = que[qh++];
for (int c = 0; c < MAX_N_ALPHA; ++c) {
Trie*v = u->ch[c];
if (v == 0)
continue;
Trie*p = u->fail;
while (p != 0 && p->ch[c] == 0)
p = p->fail;
if (p == 0)
p = trieRoot;
else
p = p->ch[c];
v->fail = p;
que[qt++] = v;
}
}
for (int i = 0; i < qh; ++i) {
Trie*t = que[i];
memset(t->fail2k, 0, sizeof t->fail2k);
t->fail2k[0] = t->fail;
for (int i = 0; i < MAX_LOG - 1; ++i) {
if (t->fail2k[i] == 0)
break;
t->fail2k[i + 1] = t->fail2k[i]->fail2k[i];
}
}
}
Trie*Left[MAX_L_PAT], *Right[MAX_L_PAT];
Trie*far[MAX_L_PAT];
Trie* isInST(int l, int r) {
if (l > r)
return trieRoot;
Trie*at = far[r];
Trie*cur = at;
int len = r - l + 1;
for (int i = MAX_LOG - 1; i >= 0; --i) {
Trie*f = cur->fail2k[i];
if (f == 0)
continue;
if (f->depth >= len)
cur = f;
}
if (cur->depth == len)
return cur;
return 0;
}
void calcRight(Trie*Right[]) {
Trie*t = trieRoot;
for (int i = 0; i < patLen; ++i) {
int cur = pat[i] - 'a';
while (t && t->ch[cur] == 0)
t = t->fail;
if (t == 0)
t = trieRoot;
else
t = t->ch[cur];
far[i] = t;
}
for (int i = 0; i < patLen; ++i) {
int l = i - 1, r = patLen;
while (l + 1 < r) {
int m = l + r >> 1;
if (isInST(i, m) != 0)
l = m;
else
r = m;
}
Right[i] = isInST(i, l);
}
}
void calcLeftAndRight() {
calcFail();
calcRight(Right);
reverse(pat, pat + patLen);
calcRight(Left);
reverse(pat, pat + patLen);
reverse(Left, Left + patLen);
}
typedef long long int64;
int64 ans = 0;
void processSplit(const Split&split) {
for (int i = 0; i < split.nBranch; ++i) {
vector<Trie*>&tmp = split.trieByBranch[i];
foreach(iter,tmp) {
Trie*u = *iter;
dataStrcut.change(u->begin, u->end, 1);
}
}
for (int i = 0; i < split.nBranch; ++i) {
vector<Trie*>&tmp = split.trieByBranch[i];
if (i != split.nBranch - 1) {
foreach(iter,tmp) {
Trie*u = *iter;
dataStrcut.change(u->begin, u->end, -1);
}
}
foreach(iter,tmp) {
Trie*u = *iter;
ans += dataStrcut.ask(u->begin, u->end);
}
if (i != split.nBranch - 1) {
foreach(iter,tmp) {
Trie*u = *iter;
dataStrcut.change(u->begin, u->end, 1);
}
}
}
for (int i = 0; i < split.nBranch; ++i) {
vector<Trie*>&tmp = split.trieByBranch[i];
foreach(iter,tmp) {
Trie*u = *iter;
dataStrcut.change(u->begin, u->end, -1);
}
}
}
void prepareDataStruct() {
dataStrcut.clear();
for (int i = 0; i < patLen; ++i) {
dataStrcut.addPoint(Left[i]->begin, Right[i]->begin);
}
dataStrcut.start();
}
void calcAns() {
ans = 0;
for (int i = 0; i < splitsCur; ++i) {
processSplit(splits[i]);
}
cout << ans << endl;
}
void work() {
doTreeSplit(vertexs + 0);
getDfsOrd();
calcLeftAndRight();
prepareDataStruct();
calcAns();
}
void solve() {
readInput();
work();
}
int main() {
solve();
}