记录编号 398372 评测结果 AAAAEEEEEEEE
题目名称 [HZOI 2016][NBUT 1653]String in the tree 最终得分 33
用户昵称 Gravatarsxysxy 是否通过 未通过
代码语言 C++ 运行时间 6.505 s
提交时间 2017-04-22 09:20:51 内存使用 0.76 MiB
显示代码纯文本
#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;
}