#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
struct custom_hash {
typedef unsigned long long ull;
const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
static ull splitmix64(ull x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(ll x) const {
return splitmix64(x + FIXED_RANDOM);
}
size_t operator()(const pair<int,int> &i)const{
return splitmix64((((ll)i.first)^(((ll)i.second)<<32))+FIXED_RANDOM);
}
};
struct RNG{
typedef unsigned long long ull;
///taken from http://prng.di.unimi.it/xoshiro256plusplus.c
ull s[4];
RNG(ull a, ull b, ull c, ull d){
///please seed this with something legit
s[0]=a,s[1]=b,s[2]=c,s[3]=d;
for (int x=0;x<1024;x++) next(); //give some random
}
static inline ull rotl(const ull x, int k){
return (x << k) | (x >> (64 - k));
}
ull next() {
const ull result = rotl(s[0] + s[3], 23) + s[0];
const ull t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rotl(s[3], 45);
return result;
}
}rng=RNG(423358081,274988025,50131061,866741066);
const int MOD=1000000007;
const ll P=583726327;
long long qexp(long long b,long long p,int m){
long long res=1;
while (p){
if (p&1) res=(res*b)%m;
b=(b*b)%m;
p>>=1;
}
return res;
}
ll fix(ll i){
while (i<0) i+=MOD;
while (MOD<=i) i-=MOD;
return i;
}
ll h[30];
ll powP[50005];
ll invP[50005];
int n;
string s;
vector<int> al[50005];
bool used[50005];
int parent[50005];
int subtree[50005];
void dfs(int i,int j){
subtree[i]=1;
for (auto it=al[i].begin();it!=al[i].end();it++){
if (!used[*it] && *it!=j){
dfs(*it,i);
subtree[i]+=subtree[*it];
}
}
}
void centroid_decomp(int i,int p,int s){
s>>=1;
dfs(i,-1);
int prev=-1;
reloop:
for (auto it=al[i].begin();it!=al[i].end();it++){
if (!used[*it] && *it!=prev && subtree[*it]>s){
prev=i;
i=*it;
goto reloop;
}
}
///i is now the centroid
used[i]=true;
parent[i]=p;
int prev_size=s-1;
for (auto it=al[i].begin();it!=al[i].end();it++){
if (!used[*it]){
if (*it!=prev){
centroid_decomp(*it,i,subtree[*it]);
s-=subtree[*it];
}
}
}
if (prev!=-1) centroid_decomp(prev,i,prev_size);
}
int BANNED; //this node cannot cross during dfs
int LENGTH; //length of palindrome we need to find
int ROOT;
int depth[50005];
unordered_map<ii,int,custom_hash> exists;
int val[500005];
int rval[500005];
vector<int> stk;
void dfs_mark(int i,int p,int id){ //this is to mark vertices during dfs
if (i==BANNED) return;
//val and rval get calculated first
depth[i]=depth[p]+1;
val[i]=(val[p]+powP[depth[i]]*h[s[i]-'a'])%MOD;
rval[i]=(rval[p]*P+h[s[i]-'a'])%MOD;
//cout<<i<<" "<<val[i]<<" "<<rval[i]<<endl;
ii temp=ii((fix(val[i]-h[s[ROOT]-'a'])*invP[1])%MOD,depth[i]);
//cout<<p<<" "<<i<<endl;
//cout<<"adding: "<<temp.fi<<" "<<temp.se<<" "<<id<<endl;
if (exists.count(temp) && exists[temp]!=id) exists[temp]=-1;
else exists[temp]=id;
for (auto &it:al[i]){
if (it==p) continue;
dfs_mark(it,i,id);
}
}
bool dfs_test(int i,int p,int id){ //test if palindrome exists
if (i==BANNED) return false;
stk.push_back(i);
if (LENGTH/2<=depth[i] && depth[i]<LENGTH){
int extra=LENGTH-depth[i]-1;
int palin=LENGTH-extra*2;
//cout<<i<<" "<<extra<<" "<<palin<<endl;
//cout<<stk[palin-1]<<endl;
if (val[stk[palin-1]]==rval[stk[palin-1]]){
ii temp=ii((fix(val[i]-val[stk[palin-1]])*invP[palin])%MOD,extra);
//cout<<temp.fi<<" "<<temp.se<<" "<<id<<endl;
if (exists.count(temp) && exists[temp]!=id) return true;
}
}
for (auto &it:al[i]){
if (it==p) continue;
if (dfs_test(it,i,id)) return true;
}
stk.pop_back();
return false;
}
bool can(int i){
if (i<2) return true;
LENGTH=i;
rep(x,1,n+1){
exists.clear();
exists[ii(0,0)]=-1;
//cout<<"trying: "<<x<<endl;
depth[x]=0;
val[x]=rval[x]=h[s[x]-'a'];
ROOT=x;
BANNED=parent[x];
for (auto &it:al[x]){
dfs_mark(it,x,it);
}
for (auto &it:al[x]){
stk.clear();
stk.push_back(x);
if (dfs_test(it,x,it)) return true;
}
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
rep(x,0,30) h[x]=rng.next()%MOD;
rep(x,0,50005){
powP[x]=qexp(P,x,MOD);
invP[x]=qexp(powP[x],MOD-2,MOD);
}
cin>>n;
cin>>s;
s="$"+s;
int a,b;
rep(x,1,n){
cin>>a>>b;
al[a].push_back(b);
al[b].push_back(a);
}
centroid_decomp(1,-1,n);
int ans=0;
int lo,hi,mi;
lo=0,hi=25005;
while (hi-lo>1){
mi=hi+lo>>1;
if (can(mi*2+1)) lo=mi;
else hi=mi;
}
ans=max(ans,lo*2+1);
lo=0,hi=25005;
while (hi-lo>1){
mi=hi+lo>>1;
if (can(mi*2)) lo=mi;
else hi=mi;
}
ans=max(ans,lo*2);
cout<<ans<<endl;
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:276:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mi=hi+lo>>1;
~~^~~
lampice.cpp:286:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mi=hi+lo>>1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
2304 KB |
Output is correct |
| 2 |
Correct |
357 ms |
2432 KB |
Output is correct |
| 3 |
Correct |
2648 ms |
2656 KB |
Output is correct |
| 4 |
Correct |
4832 ms |
2564 KB |
Output is correct |
| 5 |
Correct |
17 ms |
2304 KB |
Output is correct |
| 6 |
Correct |
17 ms |
2304 KB |
Output is correct |
| 7 |
Correct |
17 ms |
2304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5059 ms |
11688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5071 ms |
9404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
2304 KB |
Output is correct |
| 2 |
Correct |
357 ms |
2432 KB |
Output is correct |
| 3 |
Correct |
2648 ms |
2656 KB |
Output is correct |
| 4 |
Correct |
4832 ms |
2564 KB |
Output is correct |
| 5 |
Correct |
17 ms |
2304 KB |
Output is correct |
| 6 |
Correct |
17 ms |
2304 KB |
Output is correct |
| 7 |
Correct |
17 ms |
2304 KB |
Output is correct |
| 8 |
Execution timed out |
5059 ms |
11688 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
