#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
const int INF=1000000000;
int lastused[300005][26];
int edges[300005][26];
int backedge[300005];
int len[300005];
int n;
string s;
vector<int> al[50005];
int parent[50005][15];
int level[50005]; //depth idk why i used to call it level
int in[50005];
int out[50005];
int DFS_TIME=0;
void dfs(int i,int p){
in[i]=++DFS_TIME;
int curr;
for (auto it=al[i].begin();it!=al[i].end();it++){
if (*it==p) continue;
level[*it]=level[i]+1;
parent[*it][0]=i;
curr=i;
for (int x=0;parent[curr][x]!=-1;x++){
curr=parent[*it][x+1]=parent[curr][x];
}
dfs(*it,i);
}
out[i]=DFS_TIME;
}
int mov(int i,int j){
for (int x=0;x<22;x++){
if (j&1){
i=parent[i][x];
}
j>>=1;
}
return i;
}
int lca(int i,int j){
if (level[i]<level[j]) swap(i,j);
i=mov(i,level[i]-level[j]);
if (i==j) return i;
for (int x=21;x>=0;x--){
if (parent[i][x]!=parent[j][x]){
i=parent[i][x];
j=parent[j][x];
}
}
return parent[i][0];
}
int dist(int i,int j){
return level[i]+level[j]-2*level[lca(i,j)];
}
int memo[3005][3005];
int dp(int i,int j){
if (memo[i][j]!=-1) return memo[i][j];
if (s[i]!=s[j]) return -INF;
if (level[i]>level[j]) swap(i,j); //i could be ancestor of j
if (i==j) return memo[i][j]=1;
else if (parent[j][0]==i) return memo[i][j]=2;
else{
if (in[i]<=in[j] && out[j]<=out[i]){
return dp(mov(j,level[j]-level[i]-1),parent[j][0])+2;
}
else{
return dp(parent[i][0],parent[j][0])+2;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>s;
bool ST2=true;
int a,b;
for (int x=1;x<n;x++){
cin>>a>>b;
a--,b--;
al[a].push_back(b);
al[b].push_back(a);
if (a+1!=b) ST2=false;
}
memset(parent,-1,sizeof(parent));
dfs(0,-1);
if (n<=3000){
int ans=0;
memset(memo,-1,sizeof(memo));
for (int x=0;x<n;x++)
for (int y=0;y<n;y++)
ans=max(ans,dp(x,y));
cout<<ans<<endl;
}
else if (ST2){
int ans=0;
memset(edges,-1,sizeof(edges));
backedge[0]=0,backedge[1]=0;
len[0]=-1,len[1]=0;
int PREV=0;
int INDEX=1;
for (int x=0;x<s.size();x++){
while (s[x-len[PREV]-1]!=s[x])
PREV=backedge[PREV];
if (edges[PREV][s[x]-'a']==-1)
edges[PREV][s[x]-'a']=++INDEX;
int curr=edges[PREV][s[x]-'a'];
len[curr]=len[PREV]+2;
ans=max(ans,len[curr]);
if (len[curr]==1){
backedge[curr]=1;
}
else{
int b=backedge[PREV];
while (s[x-len[b]-1]!=s[x]) b=backedge[b];
backedge[curr]=edges[b][s[x]-'a'];
}
PREV=curr;
}
cout<<ans<<endl;
}
else{
int ans=0;
int counter=1;
for (int x=0;x<n;x++){
if (x && al[x].size()!=1) continue;
for (int y=x+1;y<n;y++){
if (al[y].size()!=1) continue;
string a="";
string b="";
int i=x,j=y;
while (level[i]>level[j]){
a+=s[i];
i=parent[i][0];
}
while (level[j]>level[i]){
b+=s[j];
j=parent[j][0];
}
while (i!=j){
a+=s[i];
i=parent[i][0];
b+=s[j];
j=parent[j][0];
}
reverse(b.begin(),b.end());
string t=a+s[i]+b;
//cout<<t<<endl;
backedge[0]=0,backedge[1]=0;
len[0]=-1,len[1]=0;
int PREV=0;
int INDEX=1;
for (int x=0;x<t.size();x++){
while (t[x-len[PREV]-1]!=t[x])
PREV=backedge[PREV];
if (lastused[PREV][t[x]-'a']!=counter)
edges[PREV][t[x]-'a']=++INDEX,lastused[PREV][t[x]-'a']=counter;
int curr=edges[PREV][t[x]-'a'];
len[curr]=len[PREV]+2;
ans=max(ans,len[curr]);
if (len[curr]==1){
backedge[curr]=1;
}
else{
int b=backedge[PREV];
while (t[x-len[b]-1]!=t[x]) b=backedge[b];
backedge[curr]=edges[b][t[x]-'a'];
}
PREV=curr;
}
counter++;
}
}
cout<<ans;
}
}
Compilation message
matching.cpp: In function 'int main()':
matching.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int x=0;x<s.size();x++){
~^~~~~~~~~
matching.cpp:195:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int x=0;x<t.size();x++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
39808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
39808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
39808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
39808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
39808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
