#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 = 1000001011;
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 = 546575;
void precomp() {
pw[0]=1;
for(int i=1;i<mxN;++i) pw[i]=pw[i-1]*base;
}
const int S = 20000019;
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;
mint b=0;
template<typename F> void dfsD(int at, F func) {
d++;
b+=pw[d-1]*s[at];
pref.push_back(pref.back()*base+s[at]);
vis[at]=1;
palin.push_back(pref.back()==b);
auto [g,big,val] = good();
if(g) func(val,big);
for(int to : adj[at]) if(!vis[to]) {
dfsD(to,func);
}
palin.pop_back();
pref.pop_back();
vis[at]=0;
b-=pw[d-1]*s[at];
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;
b=s[c];
dfsD(to,mycheck);
palin.pop_back();
pref.pop_back();
CHECKING=false;
d=0;
b=0;
dfsD(to,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;
pref.reserve(n+2);
palin.reserve(n+2);
for(auto& b : bf) b.v.reserve(n+2);
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';
}
Compilation message
lampice.cpp: In function 'void dfsD(int, F)':
lampice.cpp:131:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
131 | auto [g,big,val] = good();
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
6868 KB |
Output is correct |
| 2 |
Correct |
10 ms |
6996 KB |
Output is correct |
| 3 |
Correct |
25 ms |
7012 KB |
Output is correct |
| 4 |
Correct |
37 ms |
7020 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6872 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1451 ms |
10836 KB |
Output is correct |
| 2 |
Correct |
1951 ms |
10932 KB |
Output is correct |
| 3 |
Correct |
2182 ms |
11124 KB |
Output is correct |
| 4 |
Correct |
2688 ms |
11316 KB |
Output is correct |
| 5 |
Correct |
2552 ms |
11464 KB |
Output is correct |
| 6 |
Correct |
2424 ms |
11612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2339 ms |
8492 KB |
Output is correct |
| 2 |
Correct |
2755 ms |
8276 KB |
Output is correct |
| 3 |
Correct |
2485 ms |
8588 KB |
Output is correct |
| 4 |
Correct |
2600 ms |
8620 KB |
Output is correct |
| 5 |
Correct |
2555 ms |
8212 KB |
Output is correct |
| 6 |
Correct |
1634 ms |
8268 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
6868 KB |
Output is correct |
| 2 |
Correct |
10 ms |
6996 KB |
Output is correct |
| 3 |
Correct |
25 ms |
7012 KB |
Output is correct |
| 4 |
Correct |
37 ms |
7020 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6872 KB |
Output is correct |
| 8 |
Correct |
1451 ms |
10836 KB |
Output is correct |
| 9 |
Correct |
1951 ms |
10932 KB |
Output is correct |
| 10 |
Correct |
2182 ms |
11124 KB |
Output is correct |
| 11 |
Correct |
2688 ms |
11316 KB |
Output is correct |
| 12 |
Correct |
2552 ms |
11464 KB |
Output is correct |
| 13 |
Correct |
2424 ms |
11612 KB |
Output is correct |
| 14 |
Correct |
2339 ms |
8492 KB |
Output is correct |
| 15 |
Correct |
2755 ms |
8276 KB |
Output is correct |
| 16 |
Correct |
2485 ms |
8588 KB |
Output is correct |
| 17 |
Correct |
2600 ms |
8620 KB |
Output is correct |
| 18 |
Correct |
2555 ms |
8212 KB |
Output is correct |
| 19 |
Correct |
1634 ms |
8268 KB |
Output is correct |
| 20 |
Correct |
1535 ms |
7752 KB |
Output is correct |
| 21 |
Correct |
1461 ms |
7688 KB |
Output is correct |
| 22 |
Correct |
2211 ms |
7672 KB |
Output is correct |
| 23 |
Correct |
565 ms |
7940 KB |
Output is correct |
| 24 |
Correct |
2315 ms |
8452 KB |
Output is correct |
| 25 |
Correct |
2282 ms |
8244 KB |
Output is correct |
| 26 |
Correct |
2659 ms |
8680 KB |
Output is correct |
| 27 |
Correct |
2191 ms |
7740 KB |
Output is correct |
| 28 |
Correct |
2115 ms |
7784 KB |
Output is correct |
| 29 |
Correct |
2160 ms |
7780 KB |
Output is correct |
| 30 |
Correct |
2752 ms |
8972 KB |
Output is correct |
| 31 |
Correct |
1828 ms |
8088 KB |
Output is correct |
| 32 |
Correct |
1970 ms |
9572 KB |
Output is correct |
| 33 |
Correct |
1242 ms |
8304 KB |
Output is correct |
