/* Catalin-Stefan Tiseanu Pre-written code is assembled from various sources found online. Big thanks to the community for that ! */ // Pre-written code below using namespace std; #include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #include <unordered_map> #include <unordered_set> //START_CLEAN // always remove //START:mandatory #define DEBUG #ifndef NDEBUG # define assert_msg(condition, message) \ do { \ if (! (condition)) { \ std::cerr << "Assertion `" #condition "` failed in " << __FILE__ \ << " line " << __LINE__ << ": " << message << std::endl; \ std::exit(EXIT_FAILURE); \ } \ } while (false) #else # define ASSERT(condition, message) do { } while (false) #endif #ifdef DEBUG #define debug(args...) {dbg,args; cerr<<endl;} #else #define debug(args...) // Just strip off all debug tokens #endif template<class T> std::ostream& operator <<(std::ostream& stream, const vector<T> & v) { for (auto el : v) stream << el << " "; return stream; } template<class T> std::ostream& operator <<(std::ostream& stream, const vector<vector<T>> & v) { for (auto line : v) { for (auto el : line) stream << el << " "; stream << endl; } return stream; } template<class T, class U> std::ostream& operator <<(std::ostream& stream, const pair<U, T> & p) { stream << "( " << p.first << ", " << p.second << " )"; return stream; } class debugger { public: template<class T> void output (const T& v) { cerr << v << " "; } template<class T> debugger& operator , (const T& v) { output(v); return *this; } } dbg; //END:mandatory //////////////// // templates // //////////////// // general //template size template<typename T> int size(const T& c) { return int(c.size()); } //template abs template<typename T> T abs(T x) { return x < 0 ? -x : x; } //template sqr template<typename T> T sqr(T x) { return x*x; } //template remin template<typename T> bool remin(T& x, T y) { if (x <= y) return false; x = y; return true; } //template remax template<typename T> bool remax(T& x, T y) { if (x >= y) return false; x = y; return true; } //template factorize template<class T> inline vector<pair<T,int> > factorize(T n) {vector<pair<T,int> > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));} i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;} //template toStr template<typename T> string toStr(T x) { stringstream ss; ss << x; return ss.str(); } // other string maskToStr(long long x, int len) {stringstream ss; for (int i = 0; i < len; ++i) if (x >> i & 1) ss << "1"; else ss << "0"; return ss.str();} // misc #define EPS 1e-5 // types //template int64 typedef long long int64 ; //template uint64 typedef unsigned long long uint64 ; // shortcuts #define all(_xx) _xx.begin(), _xx.end() #define pb push_back #define vi vector<int> #define vs vector<string> #define vvi vector<vector<int>> #define vd vector<double> #define vpii vector<pair<int,int> > #define vpdd vector<pair<double,double> > #define pii pair<int,int> #define pll pair<long long, long long> #define pdd pair<double, double> #define mp(XX, YY) make_pair(XX, YY) #define fi first #define se second #define ll long long #define SS stringstream // for loops #define re(II, NN) for (int II(0), _NN(NN); (II) < (NN); ++(II)) #define fod(II, XX, YY) for (int II(XX), _YY(YY); (II) >= (_YY); --(II)) #define fo(II, XX, YY) for (int II(XX), _YY(YY); (II) <= (_YY); ++(II)) #define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it) // Useful hardware instructions #define bitcount __builtin_popcount #define gcd __gcd // Useful all around #define checkbit(n,b) ( (n >> b) & 1) #define DREP(a) sort(a.begin(), a.end());a.erase(unique(a.begin(), a.end()),a.end()) #define INDEX(arr,ind) (lower_bound(arr.begin(), arr.end(),ind)-arr.begin()) #define PAUSE cerr << "Press any key to continue ..."; char xxxx; scanf("%c", &xxxx); #define fill(xx,val) memset(xx, val, sizeof(xx)) struct Scanner { char* curPos; const static int BUF_SIZE = (2000000); char input[BUF_SIZE]; FILE * fin; void init(FILE * _fin) { fin = _fin; fread(input, 1, sizeof(input), fin); curPos = input; } Scanner() {;} inline void ensureCapacity() { int size = input + BUF_SIZE - curPos; if (size < 100) { memcpy(input, curPos, size); fread(input + size, 1, BUF_SIZE - size, fin); curPos = input; } } inline int nextInt() { ensureCapacity(); while (!isdigit(*curPos) && *curPos != '-') ++curPos; int res = 0; int sign = 1; if (*curPos == '-') sign = -1, ++curPos; while (*curPos >= '0' && *curPos <= '9') res = res * 10 + (*(curPos++) & 15); return sign * res; } } Sc; #define MAX_N (100111) #define MAX_LOG 19 #define N_BASES 5 int64 bases[N_BASES] = {31, 91, 151, 511, 9919}; int N, T, res, parents[MAX_N][MAX_LOG], p[MAX_N]; char S[MAX_N]; vi tree[MAX_N]; int64 down_hash[MAX_N][MAX_LOG], up_hash[MAX_N][MAX_LOG]; void df(int x, int from) { p[x] = from; for (auto v : tree[x]) { if (v != from) { df(v, x); } } } int64 single_hash(char a) { int64 res = 0; a = a - 'a' + 1; re (i, N_BASES) { res *= base[i]; res += a; } return res; } int64 combine_hash(int64 h1, int64 h2) { int64 res = h1; re (i, N_BASES) { res *= base[i]; res += base[i] / 2 + a; } res += h2; return res; } void do_parent() { fill(parents, 0); fill(p, 0); fill(up_hash, 0); fill(down_hash, 0); df(1, 0); fo (i, 1, N) parents[i][0] = p[i]; fo (j, 1, MAX_LOG - 1) { fo (i, 1, N) { parents[i][j] = parents[ parents[i][j-1] ][j - 1]; } } fo (i, 1, N) { up_hash[i][0] = down_hash[i][0] = singlehash(S[i - 1]); } fo (j, 1, MAX_LOG - 1) { fo (i, 1, N) { int log_parent = parents[i][j - 1]; up_hash[i][j] = combine_hash(up_hash[i][j-1], uphash[log_parent][j-1]); int block_parent = parents[i][j-1]; down_hash[block_parent][j] = combine_hash(down_hash[block_parent][j-1], down_hash[log_parent][j-1]); } } } int get_parent(int x, int at) { int mine = 1LL << (MAX_LOG - 1); int res = 0; fod(j, MAX_LOG - 1, 0) { if (x >= mine) { res = parents[res][j]; x -= mine; } } assert(x == 0); return res; } void doit (int x, int from, int len) { int half_len = (len + 1) / 2; int my_log = 0, po = 1; while (2 * po < half_len) { ++my_log; po *= 2; } if (len == 1) { remax(res, 1); } else if (len == 2) { if (S[x] == S[from]) remax(res, 2); } else { int pal_parent = get_parent(x, half_len - 1); pair<int64, int64> h1 = mp(down_hash[1][po], down_hash[ parents[ p[pal_parent] ][ po ] ]); pair<int64, int64> h2 = mp(up_hash[x][po], up_hash[ parents } for (auto v : tree[x]) { if (v != from) { doit(v, x, len + 1); } } } int solve() { res = 0; do_parent(); doit(1, 0, 1); return res; } int main() { Sc.init(stdin); for (T = Sc.nextInt(); T; T--) { N = Sc.nextInt(); gets(S); re (i, MAX_N) tree[i].clear(); fo (i, 1, N - 1) { int a = Sc.nextInt(), b = Sc.nextInt(); debug(a, b); tree[a].pb(b), tree[b].pb(a); } printf("%d\n", solve()); } return 0; }