#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
vector <vector <int> > g;
vector <int> _sz, h;
vector <bool> used;
bool flag;
int len;
vector <int> hash1, hash2;
map <pair <int, int>, int> mp, mp1;
vector <int> power;
const int const1 = 1e9 + 7;
void dfs1(int v, int p = -1)
{
_sz[v] = 1;
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if(to != p && !used[to])
{
h[to] = h[v] + 1;
dfs1(to, v);
_sz[v] += _sz[to];
}
}
}
void build(int v, int p = -1)
{
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if(to != p && !used[to])
{
h[to] = h[v] + 1;
build(to, v);
}
}
}
int centroid(int v, int szall, int p = -1)
{
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if(to == p || used[to])
{
continue;
}
if(_sz[to] * 2 > szall)
{
return centroid(to, szall, v);
}
}
return v;
}
vector <int> vec;
void dfs2(int v, int p)
{
int ourhash = hash1[v];
bool fl = false;
vec.push_back(v);
if(len >= h[v])
{
if(len - h[v] < h[v])
{
int len1 = len - h[v];
ourhash -= hash1[vec[vec.size() - len1 - 1]] * power[len1] % const1;
if(hash1[vec[vec.size() - len1 - 1]] == hash2[vec[vec.size() - len1 - 1]])
{
fl = true;
}
if(ourhash < 0)
{
ourhash += const1;
}
}
else
{
fl = true;
}
if(fl && mp[{ourhash, len - h[v]}] != 0)
{
flag = true;
}
}
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if(!used[to] && to != p)
{
hash1[to] = hash1[v] * 27 % const1 + s[to] - 'a' + 1;
if(hash1[to] >= const1)
{
hash1[to] -= const1;
}
hash2[to] = hash2[v] + power[h[v]] * (s[to] - 'a' + 1) % const1;
if(hash2[to] >= const1)
{
hash2[to] -= const1;
}
dfs2(to, v);
}
}
vec.pop_back();
}
vector <pair <int, int> > mass;
void dfs3(int v, int p)
{
int ourhash = hash1[v];
bool fl = false;
vec.push_back(v);
if(len >= h[v] + 1)
{
if(len - (h[v] + 1) < (h[v] + 1))
{
int len1 = len - (h[v] + 1);
ourhash -= hash1[vec[vec.size() - len1 - 1]] * power[len1] % const1;
if(ourhash < 0)
{
ourhash += const1;
}
if(hash1[vec[vec.size() - len1 - 1]] == hash2[vec[vec.size() - len1 - 1]])
{
fl = true;
}
}
else
{
fl = true;
}
if(fl)
{
mass.push_back({ourhash, h[v] + 1});
mp[{ourhash, h[v] + 1}]++;
}
}
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if(to != p && !used[to])
{
hash1[to] = hash1[v] * 27 % const1 + s[to] - 'a' + 1;
if(hash1[to] >= const1)
{
hash1[to] -= const1;
}
hash2[to] = hash2[v] + power[h[to]] * (s[to] - 'a' + 1) % const1;
if(hash2[to] >= const1)
{
hash2[to] -= const1;
}
dfs3(to, v);
}
}
vec.pop_back();
}
void go_to(int v)
{
dfs1(v);
v = centroid(v, _sz[v]);
h[v] = 0;
build(v);
used[v] = 1;
hash1[v] = hash2[v] = s[v] - 'a' + 1;
mp[{s[v] - 'a' + 1, 1}] = 1;
mass.push_back({s[v] -'a' + 1, 1});
for(int i = 0; i <g[v].size(); i++)
{
int to = g[v][i];
if(!used[to])
{
hash1[to] = hash2[to] = s[to] - 'a' + 1;
dfs2(to, v);
vec.clear();
vec.push_back(v);
hash1[to] = (s[v] - 'a' + 1) * 27 + (s[to] - 'a' + 1);
hash2[to] = (s[v] - 'a' + 1) + 27 * (s[to] - 'a' + 1);
dfs3(to, v);
vec.clear();
}
}
while(mass.size() > 0)
{
pair <int, int> v = mass.back();
mp[v]--;
mass.pop_back();
}
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if(!used[to])
{
go_to(to);
}
}
}
signed main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
cin >> n;
used.resize(n);
_sz.resize(n);
cin >> s;
power.resize(n + 1);
power[0] = 1;
for(int i = 1; i <= n; i++)
{
power[i] = power[i - 1] * 27 % const1;
}
h.resize(n);
hash1.resize(n);
hash2.resize(n);
g.resize(n);
for(int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
int l = 0, r = n / 2 + 1;
while(r - l > 1)
{
int midd = (r + l) / 2;
len = midd * 2;
for(int i = 0; i < n; i++)
{
used[i] = 0;
}
flag = false;
go_to(0);
if(flag)
{
l = midd;
}
else
{
r = midd;
}
}
int l1 = 0, r1 = n / 2 + 1;
while(r1 - l1 > 1)
{
int midd = (r1 + l1) / 2;
len = midd * 2 + 1;
for(int i = 0; i < n; i++)
{
used[i] = 0;
}
flag = false;
go_to(0);
if(flag)
{
l1 = midd;
}
else
{
r1 = midd;
}
}
cout << max(l * 2, l1 * 2 + 1);
return 0;
}
Compilation message
lampice.cpp: In function 'void dfs1(long long int, long long int)':
lampice.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'void build(long long int, long long int)':
lampice.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'long long int centroid(long long int, long long int, long long int)':
lampice.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs2(long long int, long long int)':
lampice.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs3(long long int, long long int)':
lampice.cpp:138:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'void go_to(long long int)':
lampice.cpp:168:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i <g[v].size(); i++)
~~~^~~~~~~~~~~~
lampice.cpp:189:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
120 ms |
6648 KB |
Output is correct |
| 4 |
Correct |
153 ms |
3836 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5064 ms |
135332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5087 ms |
125664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
120 ms |
6648 KB |
Output is correct |
| 4 |
Correct |
153 ms |
3836 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Execution timed out |
5064 ms |
135332 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
