Description
给出n个结点的树结构T，其中每一个结点上有一个字符，这里我们所说的字符只考虑大写字母A到Z,再给出长度为m的模式串s，其中每一位仍然是A到z的大写字母。Alice希望知道，有多少对结点<u，v>满足T上从u到V的最短路径形成的字符串可以由模式串S重复若干次得到？这里结点对<u，v>是有序的，也就是说<u，v>和<v，u>需要被区分.所谓模式串的重复，是将若干个模式串S依次相接（不能重叠).例如当S=PLUS的时候，重复两次会得到PLUSPLUS，重复三次会得到PLUSPLUSPLUS,同时要注恿，重复必须是整数次的。例如当S=XYXY时，因为必须重复整数次，所以XYXYXY不能看作是S重复若干次得到的。Input
每一个数据有多组测试， 第一行输入一个整数C，表示总的测试个数。 对于每一组测试来说： 第一行输入两个整数，分别表示树T的结点个数n与模式长度m。结点被依次编号为1到n，之后一行，依次给出了n个大写字母（以一个长度为n的字符串的形式给出），依次对应树上每一个结点上的字符（第i个字符对应了第i个结点). 之后n-1行，每行有两个整数u和v表示树上的一条无向边，之后一行给定一个长度为m的由大写字母组成的字符串，为模式串S。 1<=C<=10,3<=N<=10000003<=M<=1000000Output
给出C行，对应C组测试。每一行输出一个整数，表示有多少对节点<u,v>满足从u到v的路径形成的字符串恰好是模式串的若干次重复.Sample Input
1 11 4 IODSSDSOIOI 1 2 2 3 3 4 1 5 5 6 6 7 3 8 8 9 6 10 10 11 SDOISample Output
5字符串匹配，Hash嘛；树上操作，点分治嘛。
首先考虑如何点分，由于路径是由模式串重复多次得来的，我们没必要考虑重复了多少次，因此我们开一个桶，\(hp[i]\)表示当前匹配了模式串的前\(i\)个（在\(\%L\)意义下，\(L\)为其长度），记\(hs[i]\)表示匹配了后\(i\)个（\(pre,suf\)），在dfs过程中可以直接统计答案，然后累加
考虑如何判断dfs过程中的串是否合法，使用Hash，由于dfs过程中可能出现模式串重复多次的情况，因此我们在初始Hash的时候需要将模式串循环倍增
细节可以参考代码
/*program from Wolfycz*/#include#include #include #include #include #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline char gc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline int frd(){ int x=0,f=1; char ch=gc(); for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0'; return x*f;}inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; return x*f;}inline void print(int x){ if (x<0) putchar('-'),x=-x; if (x>9) print(x/10); putchar(x%10+'0');}const int N=1e6,base=974531;int pre[(N<<1)+10],now[N+10],child[(N<<1)+10];int size[N+10],Df[N+10],Up[N+10],Dn[N+10],sup[N+10],sdn[N+10];ull Suf[N+10],Pre[N+10];bool vis[N+10];char s[N+10];int tot,root,Max,Ans,n,m;void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}void insert(int x,int y){join(x,y),join(y,x);}void Get_root(int x,int fa,int sz){ int res=0; size[x]=1; for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){ if (son==fa||vis[son]) continue; Get_root(son,x,sz); size[x]+=size[son]; res=max(res,size[son]); } res=max(res,sz-size[x]); if (res