记录编号	377832	评测结果	AAAAAAAAAATT
题目名称	[HZOI 2016][NBUT 1653]String in the tree	最终得分	83
用户昵称	半汪	是否通过	未通过
代码语言	C++	运行时间	2.885 s
提交时间	2017-03-02 16:32:22	内存使用	1.02 MiB

#include<map>  
#include<set>  
#include<cmath>  
#include<ctime>  
#include<stack>  
#include<queue>  
#include<cstdio>  
#include<cctype>  
#include<string>  
#include<vector>  
#include<cstring>  
#include<iomanip>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#define fuck(x) cout<<"["<<x<<"]"  
#define FIN freopen("input.txt","r",stdin)  
#define FOUT freopen("output.txt","w+",stdout)  
using namespace std;  
typedef long long LL;  
typedef pair<int, int>PII;  
  
const int MX = 2e4 + 5;  
const int mod = 1e9 + 7;  
const int INF = 0x3f3f3f3f;  
  
const int seed = 131;  
typedef unsigned long long ULL;  
  
struct Edge {  
    int v, nxt;  
} E[MX];  
int Head[MX], rear;  
void edge_init() {  
    rear = 0;  
    memset(Head, -1, sizeof(Head));  
}  
void edge_add(int u, int v) {  
    E[rear].v = v;  
    E[rear].nxt = Head[u];  
    Head[u] = rear++;  
}  
  
int n;  
char S[MX];  
ULL Hash[MX], F[MX];  
LL ans[MX];  
  
bool check(int u, int v, int m) {  
    ULL h1 = Hash[u] - Hash[u - m] * F[m];  
    ULL h2 = Hash[v] - Hash[v - m] * F[m];  
    return h1 == h2;  
}  
int lcp(int u, int v) {  
    int l = 0, r = min(u, v), m;  
    while(l <= r) {  
        m = (l + r) >> 1;  
        if(check(u, v, m)) l = m + 1;  
        else r = m - 1;  
    }  
    return l - 1;  
}  
  
struct cmp {  
    bool operator()(const int &a, const int &b) {  
        int p = lcp(a, b);  
        if(a == p && b != p) return true;  
        if(b == p && a != p) return false;  
        int u = Hash[a - p] - Hash[a - p - 1] * seed;  
        int v = Hash[b - p] - Hash[b - p - 1] * seed;  
        return u < v;  
    }  
};  
set<int, cmp>W;  
  
void DFS(int u, int f, int l, LL s, ULL h) {  
    h = h * seed + S[u]; Hash[l] = h;  
    set<int, cmp>::iterator e = W.insert(l).first, e1 = e, e2 = e;  
    int Max = 0;  
  
    if(e1 != W.begin()) e1--, Max = max(Max, lcp(l, *e1));  
    if(++e2 != W.end()) Max = max(Max, lcp(l, *e2));  
    s += l - Max; ans[u] = s;  
    for(int i = Head[u]; ~i; i = E[i].nxt) {  
        int v = E[i].v;  
        if(v == f) continue;  
        DFS(v, u, l + 1, s, h);  
    }  
    W.erase(l);  
}  
  
int main() {  
	freopen("balsuffix.in","r",stdin);freopen("balsuffix.out","w",stdout); 
    F[0] = 1; //FIN;  
    for(int i = 1; i < MX; i++) {  
        F[i] = F[i - 1] * seed;  
    }  
  
    int T; scanf("%d", &T);  
    while(T--) {  
        W.clear();  
        edge_init();  
  
        scanf("%d", &n);  
        for(int i = 1; i <= n - 1; i++) {  
            int u, v;  
            scanf("%d%d", &u, &v);  
            edge_add(u, v);  
            edge_add(v, u);  
        }  
        scanf("%s", S + 1);  
        DFS(1, -1, 1, 0, 0);  
        for(int i = 1; i <= n; i++) {  
            printf("%I64d\n", ans[i]);  
        }  
    }  
    return 0;  
}