#include <bits/stdc++.h>
using namespace std;
const int N = 50004;
const long long P = 37;
const int M = 1700700007;
long long ast[N];
int n;
char u[N];
vector<int> a[N];
bool c[N];
int q[N];
void dfs0(int x, int p)
{
q[x] = 1;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (c[h] || h == p)
continue;
dfs0(h, x);
q[x] += q[h];
}
}
int dfsc(int x, int p, int xx)
{
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (c[h] || h == p)
continue;
if (q[h] > q[xx] / 2)
return dfsc(h, x, xx);
}
return x;
}
int d[N];
int up[N], down[N];
int qq;
multiset<int> s[N];
void dfs1(int x, int p)
{
if (x == p)
{
d[x] = 0;
up[x] = down[x] = u[x];
}
else
{
d[x] = d[p] + 1;
up[x] = (u[x] + P * up[p]) % M;
down[x] = (down[p] + ast[d[x]] * u[x]) % M;
}
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (c[h] || h == p)
continue;
dfs1(h, x);
}
++qq;
}
void dfs11(int x, int p, int xx)
{
s[d[x]].insert((up[x] - (up[xx] * ast[d[x]]) % M + M) % M);
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h])
continue;
dfs11(h, x, xx);
}
}
void dfs12(int x, int p, int xx)
{
s[d[x]].erase(s[d[x]].find((up[x] - (up[xx] * ast[d[x]]) % M + M) % M));
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h])
continue;
dfs12(h, x, xx);
}
}
vector<int> v;
bool dfs13(int x, int p, int m)
{
v.push_back(x);
int xx = m - (d[x] + 1);
int yy = (d[x] + 1) - xx;
if (xx >= 0 && yy >= 1)
{
if (up[v[yy - 1]] == down[v[yy - 1]])
{
if (s[xx].find((up[x] - (up[v[yy - 1]] * ast[d[x] - d[v[yy - 1]]]) % M + M) % M) != s[xx].end())
{
return true;
}
}
}
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p || c[h])
continue;
if (dfs13(h, x, m))
return true;
}
v.pop_back();
return false;
}
bool stgg(int x, int m)
{
qq = 0;
dfs1(x, x);
for (int i = 0; i <= qq; ++i)
s[i].clear();
dfs11(x, x, x);
v.clear();
v.push_back(x);
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (c[h])
continue;
dfs12(h, x, x);
if (dfs13(h, x, m))
return true;
dfs11(h, x, x);
}
return false;
}
bool stg(int m)
{
memset(c, false, sizeof c);
queue<int> q;
q.push(1);
while (!q.empty())
{
int x = q.front();
q.pop();
dfs0(x, x);
x = dfsc(x, x, x);
if (stgg(x, m))
return true;
c[x] = true;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (!c[h])
q.push(h);
}
}
return false;
}
int byn1()
{
int l = 1;
int r = n;
if (r % 2 == 0)
--r;
int ans = 0;
while (l <= r)
{
int m = (l + r) / 2;
if (m % 2 == 0)
++m;
if (stg(m))
{
ans = m;
l = m + 2;
}
else
r = m - 2;
}
return ans;
}
int byn0()
{
int l = 2;
int r = n;
if (r % 2 == 1)
--r;
int ans = 0;
while (l <= r)
{
int m = (l + r) / 2;
if (m % 2 == 1)
++m;
if (stg(m))
{
ans = m;
l = m + 2;
}
else
r = m - 2;
}
return ans;
}
int solv0()
{
int ans = 0;
for (int r = 1; r <= n; ++r)
{
dfs1(r, r);
for (int x = 1; x <= n; ++x)
{
if (up[x] == down[x])
ans = max(ans, d[x] + 1);
}
}
return ans;
}
int main()
{
//freopen("input.txt", "r", stdin);
ast[0] = 1;
for (int i = 1; i < N; ++i)
{
ast[i] = (ast[i - 1] * P) % M;
}
scanf("%d", &n);
scanf(" %s", (u + 1));
for (int i = 1; i <= n; ++i)
{
u[i] = (u[i] - 'a' + 1);
}
for (int i = 0; i < n - 1; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
printf("%d\n", solv0());
return 0;
printf("%d\n", max(byn1(), byn0()));
return 0;
}
Compilation message
lampice.cpp: In function 'void dfs0(int, int)':
lampice.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'int dfsc(int, int, int)':
lampice.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs1(int, int)':
lampice.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs11(int, int, int)':
lampice.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs12(int, int, int)':
lampice.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool dfs13(int, int, int)':
lampice.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool stgg(int, int)':
lampice.cpp:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool stg(int)':
lampice.cpp:158:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:237:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
lampice.cpp:238:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", (u + 1));
~~~~~^~~~~~~~~~~~~~~~
lampice.cpp:246:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
18 ms |
4216 KB |
Output is correct |
| 3 |
Correct |
56 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
122 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
8 ms |
4216 KB |
Output is correct |
| 6 |
Correct |
8 ms |
4344 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4216 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5060 ms |
8184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5050 ms |
7160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
18 ms |
4216 KB |
Output is correct |
| 3 |
Correct |
56 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
122 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
8 ms |
4216 KB |
Output is correct |
| 6 |
Correct |
8 ms |
4344 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4216 KB |
Output is correct |
| 8 |
Execution timed out |
5060 ms |
8184 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
