显示代码纯文本
#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <deque>
#include <cctype>
#include <map>
#include <string>
template<class T, T &zero> //zero是数组默认填充的内容。
class PersistableArray{ //可持久化数组
//其实再准确点说，是对一段内存可持久化。
//O(∩_∩)O 真是万能的方法呢？
//（但是，不同的数据结构需要的额外的空间大概也是不同的呢）
// 我们把数组可持久化，这样，用数组实现的数据结构，
// 应该就可以可持久化了。
struct node{ //咦？这是啥
node *ls, *rs;
T value;
node(){
ls = rs = NULL;
}
};
std::vector<node *> roots;
int left, right;
node *build(int l, int r){ //线段树?
if(l > r)return NULL;
node *d = new node();
if(l < r){
int m = (l+r)>>1;
d->ls = build(l, m), d->rs = build(m+1, r);
}else if(l == r)d->value = zero;
return d;
}
T query(node *d, int p, int L, int R){ //没错可持久化线段树
if(!d)return zero;
if(p == L && L == R)return d->value;
int M = (L+R)>>1;
if(p <= M)return query(d->ls, p, L, M);
else if(p > M)return query(d->rs, p, M+1, R);
}
node *modify(node *d, int p, T val, int L, int R){ //我们不搞毒瘤
if(!d)return d; //我们只是脑洞的实现者。
node *x = new node(); *x = *d;
if(p == L && R == L)x->value = val;
else{
int M = (L+R)>>1;
if(p <= M)x->ls = modify(d->ls, p, val, L, M);
else if(p > M)x->rs = modify(d->rs, p, val, M+1, R);
}
return x;
}
public:
int version; //当前版本号
void init(int start, int len){
roots.push_back(NULL);
left = start, right = start+len-1;
roots.push_back(build(left, right));
version = 1;
}
T query(int k, int p){ //查询版本k位置p上的值
if(k > roots.size())return zero;
if(p > right || p < left)return zero;
return query(roots[k], p, left, right);
}
T query(int p){
return query(version, p);
}
bool modify(int k, int p, T val, bool ct = true){ //ct 是否记录新版本
if(k > roots.size())return false; // 这个一定会产生新版本，
if(p > right || p < left)return false; // ct只是表明要不要记录它。
if(ct)roots.push_back(modify(roots[k], p, val, left, right));
else roots[k] = modify(roots[k], p, val, left, right);
return true;
}
bool modify(int p, T val, bool ct = false){ //这个modify默认不产生新版本
bool f = modify(version, p, val, ct);
if(f && ct)version += 1;
return f;
}
T operator[](int id){return query(id);}
void push(){ //产生一个当前版本的拷贝作为新版本，并改变当前版本号
roots.push_back(roots[version]);
version = roots.size()-1;
}
};
class PersistableSuffixAutomata{
//可持久化后缀自动机
//把一般的后缀自动机用到的数组，用可持久化数组实现（这脑洞）
public:
typedef std::map<int, int> trans;
static int int_zero;
static int int_one;
PersistableArray<int, int_zero> len, link;
PersistableArray<int, int_one> last, cnt;
static trans empty_trans;
PersistableArray<trans, empty_trans> next;
PersistableSuffixAutomata(int rev){
len.init(1, rev);
link.init(1, rev);
next.init(1, rev);
last.init(1, 1);
cnt.init(1, 1);
}
void preview(){ //见 PersistableArray#push
len.push();
link.push();
next.push();
last.push();
cnt.push();
}
void set_version(int ver){
len.version = ver;
link.version = ver;
next.version = ver;
last.version = ver;
cnt.version = ver;
}
void extend(int c){
preview(); //推♂倒旧版本
int cur = cnt[1]+1; cnt.modify(1, cur);
len.modify(cur, len[last[1]]+1);
int p;
for(p = last[1]; p && !next[p][c]; p = link[p]){
trans t = next[p]; t[c] = cur;
next.modify(p, t);
}
if(!p)link.modify(cur, 1);
else{
int q = next[p][c];
if(len[q] == len[p]+1)link.modify(cur, q);
else{
int clone = cnt[1]+1; cnt.modify(1, clone);
link.modify(clone, link[q]);
len.modify(clone, len[p]+1);
next.modify(clone, next[q]);
for(; p && next[p][c] == q; p = link[p]){
trans t = next[p]; t[c] = clone;
next.modify(p, t);
}
link.modify(cur, clone);
link.modify(q, clone);
}
}
last.modify(1, cur);
}
};
int PersistableSuffixAutomata::int_zero = 0;
int PersistableSuffixAutomata::int_one = 1;
std::map<int, int> PersistableSuffixAutomata::empty_trans = std::map<int, int>();
//真是不优美，c++98并不滋瓷右值引用，现在这个实现方式真是难看。。。
namespace IO{
char buf[1<<18], *fs, *ft;
inline char readc(){
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}
inline int readint(){
char c; int r;
while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
return r;
}
inline int read_string(char *str){
int len = 1;char c;
while(!isalpha(c = readc()));str[0] = c;
while(isalpha(c = readc()))str[len++] = c;
str[len] = 0;
return len;
}
};using IO::read_string; using IO::readint;
const int MAXN = 1e4+10;
std::vector<int> G[MAXN];
char str[MAXN];
int val[MAXN];
int ans[MAXN];
int cver;
void dfs(int u, int f, PersistableSuffixAutomata &sam){
sam.extend(val[u]);
int ver = cver;
ans[u] = ans[f]+sam.len[sam.last[1]]-sam.len[sam.link[sam.last[1]]];
for(int i = 0; i < G[u].size(); i++){
int to = G[u][i];
if(f != to){
sam.set_version(ver);
cver++;
dfs(to, u, sam);
}
}
}
int main(){
//freopen("test_data.out", "r", stdin);
freopen("balsuffix.in", "r", stdin);
freopen("balsuffix.out", "w", stdout);
int T = readint();
while(T--){
int n = readint();
for(int i = 1; i < n; i++){
int x = readint(); int y = readint();
G[x].push_back(y); G[y].push_back(x);
}
read_string(str);
PersistableSuffixAutomata sam(n*2+5);
for(int i = 1; i <= n; i++)val[i] = str[i-1]-'a', ans[i] = 0;
cver = 2;
dfs(1, 0, sam);
for(int i = 1; i <= n; i++)printf("%d\n", ans[i]);
for(int i = 1; i <= n; i++)G[i].clear();
}
return 0;
}
sxysxy