#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 5e4+1, oo = 1e9;
const long long MD = 1e9+9;
template<long long MOD=MD> struct mdint {
int d=0;
mdint () {d=0;}
mdint (long long _d) : d(_d%MOD){
if(d<0) d+=MOD;
};
friend mdint& operator+=(mdint& a, const mdint& o) {
a.d+=o.d; if(a.d>=MOD) a.d-=MOD;
return a;
}
friend mdint& operator-=(mdint& a, const mdint& o) {
a.d-=o.d; if(a.d<0) a.d+=MOD;
return a;
}
friend mdint& operator*=(mdint& a, const mdint& o) {
return a = mdint((ll)a.d*o.d);
}
mdint operator*(const mdint& o) const {
mdint res = *this;
res*=o;
return res;
}
mdint operator+(const mdint& o) const {
mdint res = *this;
res+=o;
return res;
}
mdint operator-(const mdint& o) const {
mdint res = *this;
res-=o;
return res;
}
mdint operator^(long long b) const {
mdint tmp = 1;
mdint power = *this;
while(b) {
if(b&1) {
tmp = tmp*power;
}
power = power*power;
b/=2;
}
return tmp;
}
friend mdint operator/=(mdint& a, const mdint& o) {
a *= (o^(MOD-2));
return a;
}
mdint operator/(const mdint& o) {
mdint res = *this;
res/=o;
return res;
}
bool operator==(const mdint& o) { return d==o.d;}
bool operator!=(const mdint& o) { return d!=o.d;}
friend istream& operator>>(istream& c, mdint& a) {return c >> a.d;}
friend ostream& operator<<(ostream& c, const mdint& a) {return c << a.d;}
};
using mint = mdint<MD>;
mint pw[mxN];
const mint base = 123346;
void precomp() {
pw[0]=1;
for(int i=1;i<mxN;++i) pw[i]=pw[i-1]*base;
}
const int S = 10000019;
struct bloomfilter {
bitset<S> bs = {};
vi v;
bool check(ll i) {
return bs[i%S] and bs[(i*6755^1244546)%S];
}
void clear() {
for(auto i : v) {
add(i,0);
}
v.clear();
}
void add(ll i, bool s=1) {
if(s) v.push_back(i);
bs[i%S]=bs[(i*6755^1244546)%S]=s;
}
} bf[2];
bitset<mxN> vis;
basic_string<int> adj[mxN];
int sz[mxN];
string s;
void dfsz(int at) {
vis[at]=1;
sz[at]=1;
for(int to : adj[at]) if(!vis[to]) {
dfsz(to);
sz[at]+=sz[to];
}
vis[at]=0;
}
int LEN;
vector<char> palin = {1};
vector<mint> pref = {0};
int d=1;
bool CHECKING=false;
tuple<bool,bool,int> good() {
int check = min(d,LEN-d);
if(d>check) {
if(!palin[d-check]) return {0,0,0};
}
return {true, d >= (LEN+1 + !CHECKING)/2, (pref.back()- pw[check]*pref[d-check]).d};
}
bool foundLEN=false;
template<typename F> void dfsD(int at, mint f, mint b, F func) {
d++;
f=f*base+s[at];
b+=pw[d-1]*s[at];
pref.push_back(f);
vis[at]=1;
palin.push_back(f==b);
auto [g,big,val] = good();
if(g) func(val,big);
for(int to : adj[at]) if(!vis[to]) {
d++;
dfsD(to,f,b,func);
d--;
}
palin.pop_back();
pref.pop_back();
vis[at]=0;
d--;
}
int centroid(int at) {
int total=sz[at], from=-1;
while(true) {
bool f=false;
for(int to : adj[at]) if(to!=from and !vis[to]) {
if(sz[to]*2>total) {
from=at;
at=to;
f=true;
break;
}
}
if(!f) return at;
}
}
bool decomp(int at) {
dfsz(at);
int c = centroid(at);
vis[c]=1;
for(int to : adj[c]) if(!vis[to]) {
if(decomp(to)) {
vis[c]=0;
return true;
}
}
// now the real work.
bf[0].add(0);
for(int to : adj[c]) if(!vis[to]) {
auto mycheck = [&](int v, bool big) {
if(bf[!big].check(v)) {
foundLEN=true;
}
};
auto myadd = [&](int v, bool big) {
bf[big].add(v);
};
d=1;
palin.push_back(1);
pref.push_back(s[c]);
CHECKING=true;
dfsD(to,s[c],s[c],mycheck);
palin.pop_back();
pref.pop_back();
CHECKING=false;
d=0;
dfsD(to,0,0,myadd);
if(foundLEN) break;
}
bf[0].clear();
bf[1].clear();
vis[c]=0;
return foundLEN;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precomp();
int n; cin >> n;
cin >> s;
for(int i=0;i<n-1;++i) {
int a,b; cin >> a >> b,--a,--b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int lo = 0,hi=n/2;
while(lo<hi) {
int mid = (lo+hi+1)/2;
LEN = mid*2;
foundLEN=0;
if(decomp(0)) {
lo = mid;
} else hi = mid-1;
}
int ans=lo*2;
lo=0,hi = (n-1)/2;
while(lo<hi) {
int mid = (lo+hi+1)/2;
LEN = mid*2+1;
foundLEN=0;
if(decomp(0)) {
lo = mid;
} else hi = mid-1;
}
ans = max(ans,lo*2+1);
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
91 ms |
16768 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2119 ms |
6424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
