This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e4 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;
vector<ll> g[N];
char c;
int n,x,y,dep[N],child[N],ans = 1,ban[N],need,mu[N],a[N],pv[N],h[N],par[N];
unordered_multiset<int> s;
ll up[N],down[N];
void DFSinit(ll u,ll p,ll d){
child[u] = 1; par[u] = p; dep[d] = u; h[u] = d;
down[u] = (ll)down[p]*base + a[u]; down[u] %= mod;
up[u] = (ll)a[u]*mu[d - 1] + up[p]; up[u] %= mod;
if (d > need/2){
ll t = need - d; pv[u] = dep[d - t];
}
for (auto i : g[u]) if (i != p && !ban[i]){
DFSinit(i,u,d + 1); child[u] += child[i];
}
}
ll Findcent(ll u,ll p,ll sz){
ll mx = 0;
for (auto i : g[u]) if (i != p&& !ban[i]){
if (child[mx] < child[i]) mx = i;
}
int rm = sz - child[u];
if (max(rm,child[mx])*2 <= sz) return u;
return Findcent(mx,u,sz);
}
void Erase(ll u,ll p){
s.erase(s.find(down[u]));
for (auto i : g[u])
if (i != p && !ban[i]) Erase(i,u);
}
void Insert(ll u,ll p){
s.insert(down[u]);
for (auto i : g[u])
if (i != p && !ban[i]) Insert(i,u);
}
bool DFS(ll u,ll p){
if (h[u] > need) return 0;
if (h[u] > need/2){
ll C = pv[u];
//cout<<up[C]<<" "<<down[C]<<"x"; exit(0);
ll AC = ((ll) down[u] - (ll) down[par[C]]*mu[h[u] - h[C] + 1] + mod*mod)%mod;
if (s.find(AC) != s.end() && up[C] == down[C]) {
return 1;
}
}
for (auto i : g[u]) if (i != p&& !ban[i]){
if (DFS(i,u)) return 1;
}
return 0;
}
bool solve(ll r){
DFSinit(r,0,1);
ll cent = Findcent(r,0,child[r]);
DFSinit(cent,0,1); s.clear(); Insert(cent,0);
for (auto i : g[cent]) if (!ban[i]){
Erase(i,cent);
if (DFS(i,cent)) return 1;
Insert(i,cent);
}
ban[cent] = 1;
for (auto i : g[cent])
if (!ban[i] && solve(i)) return 1;
return 0;
}
bool chk(ll mid){
need = mid;
memset(ban,0,sizeof(ban));
return solve(1);
}
void BS(int inc){
int l,m,h; l = 1; h = n/2;
if (h*2 + inc > n) h--;
while(l <= h){
m = (l + h)/2;
if (chk(m*2 + inc)) l = m + 1;
else h = m - 1;
}
ans = max(ans,h*2 + inc);
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
}
cin>>n; mu[0] = 1;
for (ll i = 1;i <= n + 3;i++){
if (i <= n) cin>>c,a[i] = c - 'a' + 1;
ll now = (ll) mu[i - 1]*base; now %= mod;
mu[i] = now;
}
for (ll i = 1;i < n;i++){
cin>>x>>y;
g[x].push_back(y); g[y].push_back(x);
}
//debug(chk(3));
BS(0); BS(1);
cout<<ans;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message (stderr)
lampice.cpp: In function 'int main()':
lampice.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |