fork download
copy 
  1. // icebear
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int MOD = 1e9 + 2277;
  6. const int base = 311;
  7. const int N = 50000 + 5;
  8. int n, power[N];
  9. char c[N];
  10. vector<int> G[N];
  11. int sz[N];
  12. bool isCentroid[N];
  13.  
  14. void dfs(int u, int par) {
  15.     sz[u] = 1;
  16.     for(int v : G[u]) if (v != par && !isCentroid[v]) {
  17.         dfs(v, u);
  18.         sz[u] += sz[v];
  19.     }
  20. }
  21.  
  22. int findCentroid(int u, int par, const int &subtree) {
  23.     for(int v : G[u]) if (v != par && !isCentroid[v] && sz[v] * 2 > subtree)
  24.         return findCentroid(v, u, subtree);
  25.     return u;
  26. }
  27.  
  28. int pref[N], suff[N], depth[N];
  29. unordered_map<int, bool> hsh[N];
  30. int length, maxLen;
  31.  
  32. bool calcAns(int u, int par, bool answer) {
  33.     depth[u] = depth[par] + 1;
  34.     if (depth[u] > length) return false;
  35.     maxLen = max(maxLen, depth[u]);
  36.  
  37.     pref[u] = (1LL * pref[par] * base + c[u]) % MOD;
  38.     suff[u] = (suff[par] + 1LL * c[u] * power[depth[u] - 1]) % MOD;
  39.  
  40.     if (answer) {
  41.         if (pref[u] == suff[u] && depth[u] >= length && depth[u] % 2 == length % 2)
  42.             return true;
  43.         // pref[B] + suff[A] * T^len(B) = pref[A] + suff[B] * T^len(A)
  44.         int curHash = (1LL * suff[u] * power[length - depth[u]] - pref[u] + MOD) % MOD;
  45.         if (hsh[length - depth[u]].find(curHash) != hsh[length - depth[u]].end())
  46.             return true;
  47.     } else {
  48.         int curHash = (1LL * suff[u] * power[length - depth[u]] - pref[u] + MOD) % MOD;
  49.         hsh[depth[u]][curHash] = true;
  50.     }
  51.  
  52.     for(int v : G[u]) if (v != par && !isCentroid[v]) {
  53.         if (calcAns(v, u, answer)) return true;
  54.     }
  55.     return false;
  56. }
  57.  
  58. bool buildCentroid(int u)  {
  59.     dfs(u, -1);
  60.     int centroid = findCentroid(u, -1, sz[u]);
  61.     isCentroid[centroid] = true;
  62.     maxLen = 0;
  63.  
  64.     for(int v : G[centroid]) if (!isCentroid[v]) {
  65.         pref[centroid] = suff[centroid] = c[centroid];
  66.         depth[centroid] = 1;
  67.         if (calcAns(v, centroid, true)) return true;
  68.         pref[centroid] = suff[centroid] = 0;
  69.         depth[centroid] = 0;
  70.         calcAns(v, centroid, false);
  71.     }
  72.  
  73.     for(int i = 0; i <= maxLen; i++) hsh[i].clear();
  74.  
  75.     for(int v : G[centroid]) if (!isCentroid[v] && buildCentroid(v))
  76.         return true;
  77.     return false;
  78. }
  79.  
  80. int main() {
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0); cout.tie(0);
  83.     cin >> n;
  84.     for(int i = 1; i <= n; i++) cin >> c[i];
  85.     for(int i = 1; i < n; i++) {
  86.         int u, v;
  87.         cin >> u >> v;
  88.         G[u].push_back(v);
  89.         G[v].push_back(u);
  90.     }
  91.     power[0] = 1;
  92.     for(int i = 1; i <= n; i++) power[i] = 1LL * power[i - 1] * base % MOD;
  93.  
  94.     int low = 1, high = n / 2, res = 0;
  95.     while(low <= high) {
  96.         int mid = (low + high) >> 1;
  97.         length = 2 * mid;
  98.         for(int i = 1; i <= n; i++) isCentroid[i] = false;
  99.         if (buildCentroid(1)) res = length, low = mid + 1;
  100.         else high = mid - 1;
  101.     }
  102.  
  103.     low = 0, high = (n - 1) / 2;
  104.     while(low <= high) {
  105.         int mid = (low + high) >> 1;
  106.         length = 2 * mid + 1;
  107.         for(int i = 1; i <= n; i++) isCentroid[i] = false;
  108.         if (buildCentroid(1)) res = max(res, length), low = mid + 1;
  109.         else high = mid - 1;
  110.     }
  111.     cout << res;
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0.01s 8240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rAOLsD
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!