#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 5e4 + 2;
vector<vector<int> > g(N , vector<int>());
int ans = 0;
string all;
string walk = "";
bool good(string cur) {
string other = cur;
reverse(other.begin() , other.end());
return other == cur;
}
void dfs(int v , int p = -1) {
walk.push_back(all[v - 1]);
if (good(walk)) {
ans = max(ans , (int)walk.size());
}
for (int to : g[v]) {
if (to != p) {
dfs(to , v);
walk.pop_back();
}
}
}
//hashing
int gen_base(const int before , const int after) {
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 mt_rand(seed);
int base = uniform_int_distribution<int>(before + 1, after)(mt_rand);
return base % 2 == 0 ? base - 1 : base;
}
struct PolyHash {
static const int mod = (int)1e9 + 123;
static vector<int> pow1;
static vector<ull> pow2;
static int base;
static inline int diff(int a , int b) {
return (a -= b) < 0 ? a + mod : a;
}
vector<int> pref1;
vector<ull> pref2;
PolyHash(const string s) : pref1(s.size() + 1u , 0) , pref2(s.size() + 1u , 0) {
assert(base < mod);
const int n = s.size();
while ((int)pow1.size() <= n) {
pow1.push_back(1LL * pow1.back() * base % mod);
pow2.push_back(pow2.back() * base);
}
for (int i = 0; i < n; i++) {
assert(base > s[i]);
pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
pref2[i + 1] = pref2[i] + s[i] * pow2[i];
}
}
inline pair<int , ull> operator()(const int pos , const int len , const int mxPow = 0) const {
int hash1 = pref1[pos + len] - pref1[pos];
ull hash2 = pref2[pos + len] - pref2[pos];
if (hash1 < 0) hash1 += mod;
if (mxPow != 0) {
hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;
hash2 *= pow2[mxPow - (pos + len - 1)];
}
return make_pair(hash1 , hash2);
}
};
int PolyHash::base((int)1e9 + 7);
vector<int> PolyHash::pow1{1};
vector<ull> PolyHash::pow2{2};
int getMaxPalindromic(string a) {
int result = 0;
PolyHash::base = gen_base(256 , PolyHash::mod);
string b(a);
reverse(b.begin() , b.end());
PolyHash hash_a(all) , hash_b(b);
for (int i = 0 , j = n - 1; i < n; i++ , j--) {
int low = 0 , high = min(n - i , n - j) + 1;
while (high - low > 1) {
int mid = (low + high) >> 1;
if (hash_a(i , mid , n) == hash_b(j , mid , n)) {
low = mid;
} else {
high = mid;
}
}
result = max(result , 2 * low - 1);
low = 0 , high = min(n - i - 1 , n - j) + 1;
while (high - low > 1) {
int mid = (high + low) >> 1;
if (hash_a(i + 1 , mid , n) == hash_b(j , mid , n)) {
low = mid;
} else {
high = mid;
}
}
result = max(result , 2 * low);
}
return result;
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
int n;
cin >> n;
cin >> all;
bool subtask2 = true;
for (int i = 1; i < n; i++) {
int u , v;
cin >> u >> v;
if (u + 1 != v) {
subtask2 = false;
}
g[u].push_back(v);
g[v].push_back(u);
}
if (n <= 3000) {
//solve subtask 1
for (int i = 1; i <= n; i++) {
walk = "";
dfs(i);
}
cout << ans << '\n';
return 0;
}
if (subtask2) {
//solve subtask 2
cout << getMaxPalindromic(all) << '\n';
return 0;
}
return 0;
}
Compilation message
lampice.cpp: In function 'int getMaxPalindromic(std::__cxx11::string)':
lampice.cpp:91:25: error: 'n' was not declared in this scope
for (int i = 0 , j = n - 1; i < n; i++ , j--) {
^
