#include <bits/stdc++.h>
#include<unordered_map>
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;
std::unordered_map <int, int> mp;
std::unordered_map<int, int> 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 = hash2[v];
bool fl = false;
vec.push_back(v);
if(len >= h[v])
{
if(len - h[v] < h[v])
{
int len1 = len - h[v];
ourhash -= hash2[vec[vec.size() - len1 - 1]];
if(hash1[vec[vec.size() - len1 - 1]] == hash2[vec[vec.size() - len1 - 1]])
{
fl = true;
}
if(ourhash < 0)
{
ourhash += const1;
}
}
else
{
fl = true;
}
ourhash = ourhash * power[len - h[v]] % const1;
if(fl && mp[ourhash] != 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 = hash2[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 -= hash2[vec[vec.size() - len1 - 1]] % const1;
if(ourhash < 0)
{
ourhash += const1;
}
if(hash1[vec[vec.size() - len1 - 1]] == hash2[vec[vec.size() - len1 - 1]])
{
fl = true;
}
}
else
{
fl = true;
}
ourhash = ourhash * power[len - h[v] - 1] % const1;
if(fl)
{
mass.push_back({ourhash, h[v] + 1});
mp[ourhash]++;
}
}
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;
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.first]--;
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:22: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:35: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:47: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:92: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:144: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:174:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i <g[v].size(); i++)
~~~^~~~~~~~~~~~
lampice.cpp:195: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 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5085 ms |
425436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5061 ms |
240480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
