先一道一道题慢慢补上，
1009.题意，一棵N(N<=50000)个节点的树，每个节点上有一个字母值，给定一个串S0(|S0| <=30)，q个询问，(q<=50000)，每次询问经过两个点u，v之间的路径上的字母构成字符串S，问S0在S中作为序列出现了多少次。
分析：对于每次询问需要知道其LCA，设w = LCA(u, v),可以用tarjan处理出来，或者倍增法也行。然后w会将S0分成两部分，记做S1，S2，然后分别考虑S1在u->w的路径出现次数，以及S2在v->w出现的次数。
S1(x) = S0[1....x]，1<=x<=|S0|.
以S1为例，需要预处理出来u到根节点的路径上对应S0[i,j]序列出现的次数，设为dp1[u][i][j],然后S1(x)在u->w出现的次数记为t1[x],那么
t1[x] = dp1[u][1][x] - sum{t1[a-1]*dp1[fa[w]][a][x]} （1<=a<=x)
而dp1[u][1][x] 可以在tarjan求LCA时候预处理出来，转移dp1[u][i][j] = dp1[fa[u]][i][j] + (nd[u] == S0[i])*dp1[fa[u]][i+1][j];
对于S2也是可以同样考虑的。
注意：占用内存很大，需要用16位节省内存，dfs的话还需要扩栈，实现时发现不能随便用unsigned short,因为变成负数的话会相当于mod 2^16这个是会导致WA的。
代码：
#pragma comment(linker, "/STACK:16777216")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define in freopen("solve_in.txt", "r", stdin);
#define Rep(i, base, n) for(int i = (base); i < n; i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define VREP(i, n, base) for(int i = (n); i >= (base); i--)
#define SET(a, n) memset(a, (n), sizeof(a));
#define pb push_back
#define mp make_pair using namespace std;
typedef vector<unsigned short> VI;
typedef pair<unsigned short, unsigned short> PII;
typedef vector<PII> VII;
typedef long long LL; const int maxn = + ;
const int maxm = ;
const int M = ; short dp1[maxn][maxm][maxm], dp2[maxn][maxm][maxm];
bool vis[maxn];
int len;
char s[maxm], nd[maxn];
unsigned short pa[maxn]; VI g[maxn];
unsigned short lca[maxn];
VII que[maxn];
VII qq; unsigned short findset(unsigned short x) {
return x == pa[x] ? x : pa[x] = findset(pa[x]);
} void init(int n) {
qq.clear();
REP(i, n+) {
que[i].clear();
g[i].clear();
vis[i] = false;
REP(j, maxm) REP(k, maxm) {
dp1[i][j][k] = , dp2[i][j][k] = ;
if(j > k)
dp1[i][j][k] = ;
if(j < k)
dp2[i][j][k] = ;
}
}
}
int n, m;
short t1[maxm], t2[maxm];
void tarjan(int u, int fa) {
pa[u] = u;
if(!fa) {
Rep(i, , len+)
if(s[i] == nd[u]) {
dp1[u][i][i] = dp2[u][i][i] = ;
}
} else {
int v = u;
u = fa;
Rep(i, , len+) Rep(j, , len+) {
if(i >= j) {
dp2[v][i][j] = (dp2[v][i][j] + dp2[u][i][j] + (nd[v] == s[i])*(dp2[u][i-][j]))%M;
}
if(dp2[v][i][j] < )
dp2[v][i][j] += M;
if(i <= j) {
dp1[v][i][j] = (dp1[v][i][j] + dp1[u][i][j] + (nd[v] == s[i])*(dp1[u][i+][j]))%M;
}
if(dp1[v][i][j] < )
dp1[v][i][j] += M;
}
u =v;
}
vis[u] = true;
REP(i, g[u].size()) {
int v = g[u][i];
if(v == fa)
continue;
tarjan(v, u);
pa[v] = u;
}
REP(i, que[u].size()) {
int v = que[u][i].first;
int id = que[u][i].second;
if(!vis[v])
continue;
lca[id] = findset(v);
}
}
void solve() {
REP(ii, m) {
int w = lca[ii];
int u = qq[ii].first;
int v = qq[ii].second;
if(u == v) {
printf("%d\n", len == && s[] == nd[u]);
continue;
}
SET(t1, );
SET(t2, );
t1[] = t2[len+] = ;
if(w != u) {
Rep(i, , len+) {
int tmp = ;
Rep(x, , i+) {
tmp = (tmp + ((LL)t1[x-]*dp1[w][x][i])%M)%M;
}
t1[i] = (dp1[u][][i]-tmp)%M;
if(t1[i] < )
t1[i] += M;
}
}
if(w != v) {
VREP(i, len, ) {
int tmp = ;
VREP(x, len, i) {
tmp = (tmp + ((LL)t2[x+]*dp2[w][x][i])%M)%M;
}
t2[i] = (dp2[v][len][i] - tmp)%M;
if(t2[i] < )
t2[i] += M;
}
}
int ans = ;
REP(i, len+) {
if(s[i] == nd[w])
ans = (ans + ((LL)t1[i-]*t2[i+])%M)%M;
ans = (ans + ((LL)t1[i]*t2[i+])%M)%M;
if(ans < )
ans += M;
}
if(ans < )
ans += M;
printf("%d\n", ans);
}
}
int main() { int T;
for(int t = scanf("%d", &T); t <= T; t++) {
scanf("%d%d", &n, &m);
init(n);
REP(i, n-) {
int u, v;
scanf("%d%d", &u, &v);
g[u].pb(v);
g[v].pb(u);
}
s[] = '\0';
scanf("%s%s", nd+, s+);
len = strlen(s+);
REP(i, m) {
int u, v;
scanf("%d%d", &u, &v);
qq.pb(mp(u, v));
que[u].pb(mp(v, i));
que[v].pb(mp(u, i));
}
tarjan(, );
solve();
}
return ;
}