C++11(clang++ 3.9) 解法, 执行用时: 2340ms, 内存消耗: 20064K, 提交时间: 2019-12-08 19:54:49

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e4+5,mod=10007;
struct node
{
    short a[6][6];
    node(){memset(a,0,sizeof(a));}
}t[N<<2][2];
char s[N];
int n,q,head[N],si[N],id,f[N],rev[N],dep[N],son[N],fa[N],top[N],nex[N<<1],to[N<<1];
int tot=1;void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
node ans;
node Merge(node a,node b)
{
    register int i,j,k;
    for(i=1;i<=5;i++)
        for(j=i;j<=5;j++)
        ans.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
    for(i=1;i<=5;i++)
        for(j=1;j<=5;j++)
        for(k=j+1;k<=5;k++)
        ans.a[i][k]=(ans.a[i][k]+(int)a.a[i][j]*b.a[j+1][k])%mod;
    return ans;
}
void build(int l,int r,int k)
{
    if(l==r)
    {
        if(s[rev[l]]=='A')
            t[k][0].a[1][1]=t[k][0].a[5][5]=1;
        if(s[rev[l]]=='B')
            t[k][0].a[2][2]=t[k][0].a[4][4]=1;
        if(s[rev[l]]=='C')
            t[k][0].a[3][3]=1;
        t[k][1]=t[k][0];
        return;
    }
    int m=l+r>>1;
    build(l,m,k<<1);build(m+1,r,k<<1|1);
    t[k][0]=Merge(t[k<<1][0],t[k<<1|1][0]);
    t[k][1]=Merge(t[k<<1|1][1],t[k<<1][1]);
}
node query(int l,int r,int k,int x,int y,int opt)
{
    if(r<x||l>y) return node();
    if(l>=x&&r<=y) return t[k][opt];
    int m=l+r>>1;
    return opt?Merge(query(m+1,r,k<<1|1,x,y,opt),query(l,m,k<<1,x,y,opt)):Merge(query(l,m,k<<1,x,y,opt),query(m+1,r,k<<1|1,x,y,opt));
}
void dfs1(int u,int p)
{
    si[u]=1;fa[u]=p;dep[u]=dep[p]+1;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==p) continue;
        dfs1(v,u);si[u]+=si[v];
        if(si[v]>si[son[u]]) son[u]=v;
    }
}
void dfs2(int u)
{
    f[u]=++id;rev[id]=u;
    if(son[u]) top[son[u]]=top[u],dfs2(son[u]);
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa[u]||v==son[u]) continue;
        top[v]=v;dfs2(v);
    }
}
int Q(int u,int v)
{
    node ansu,ansv;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]]) ansu=Merge(query(1,n,1,f[top[u]],f[u],0),ansu),u=fa[top[u]];
        else ansv=Merge(ansv,query(1,n,1,f[top[v]],f[v],1)),v=fa[top[v]];
    }
    if(dep[u]>dep[v]) return Merge(Merge(ansv,query(1,n,1,f[v],f[u],0)),ansu).a[1][5];
    else return Merge(Merge(ansv,query(1,n,1,f[u],f[v],1)),ansu).a[1][5];
}
int main()
{
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);
    }
    dfs1(1,0);top[1]=1;
    dfs2(1);
    build(1,n,1);
    while(q--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",Q(u,v));
    }
}