fork download
copy 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define ld long double
  6. #define eb emplace_back
  7. #define ef emplace_front
  8. #define pii pair <int, int>
  9. #define pli pair <ll, int>
  10. #define pll pair <ll, ll>
  11. #define pci pair <char, int>
  12. #define pil pair <int, ll>
  13. #define pic pair <int, char>
  14. #define pib pair <int, bool>
  15. #define pbi pair <bool, int>
  16. #define pcc pair <char, char>
  17. #define fi first
  18. #define se second
  19. #define all(ac) ac.begin(), ac.end()
  20. #define MASK(x) (1 << (x))
  21. #define ub(i, j) (((i) >> (j)) & 1)
  22. #define FBIT(x) (MASK(x) - 1)
  23. #define FLIP(x, y) (FBIT(x) ^ (y))
  24. #define bit_count(x) (int) (__builtin_popcount(x))
  25. #define bit_countll(x) (int) (__builtin_popcountll(x))
  26. #define ii make_pair
  27. #define int128 __int128_t
  28. #define SZ(x) ((int) x.size())
  29. #define multi 0
  30.  
  31. const int MX = 4e4 + 4;
  32. int n;
  33. char ch[MX];
  34. int w[MX];
  35.  
  36. struct node {
  37.     int w, mx, mn;
  38.     node(int w = 0, int mx = 0, int mn = 0): w(w), mx(mx), mn(mn) {}
  39. };
  40.  
  41. vector <int> G[MX];
  42. int sz[MX];
  43. bool del[MX];
  44.  
  45. int DFS(int u, int par) {
  46.     sz[u] = 1;
  47.     for(int &v : G[u]) if(!del[v] && v != par) {
  48.         sz[u] += DFS(v, u);
  49.     }
  50.  
  51.     return sz[u];
  52. }
  53.  
  54. int find_centroid(int u, int par, int half) {
  55.     for(int &v : G[u]) if(!del[v] && sz[v] > half && v != par) {
  56.         return find_centroid(v, u, half);
  57.     }
  58.  
  59.     return u;
  60. }
  61.  
  62. int fd[MX << 1], fu[MX << 1];
  63. int res;
  64. vector <node> cur;
  65.  
  66. void DFS2(int u, int par, node tmp) {
  67.     cur.eb(tmp);
  68.     for(int &v : G[u]) if(!del[v] && v != par) {
  69.         int cw = w[ch[v]];
  70.         DFS2(v, u, node(tmp.w + cw, max(tmp.mx, tmp.w + cw), min(tmp.mn, tmp.w + cw)));
  71.     }
  72.  
  73.     return;
  74. }
  75.  
  76. void solve(int u) {
  77.     int root = find_centroid(u, -1, DFS(u, -1) >> 1);
  78.     del[root] = 1;
  79.  
  80.     int w_root = w[ch[root]];
  81.     if(w_root > 0) fu[w_root + MX] = 1;
  82.     fd[MX] = 0;
  83.  
  84.     vector <int> tr = {MX, w_root + MX};
  85.     for(int &v : G[root]) if(!del[v]) {
  86.         DFS2(v, -1, node(w[ch[v]], max(0, w[ch[v]]), min(w[ch[v]], 0)));
  87.  
  88.         for(node x : cur) {
  89.             if(x.mn == x.w && fu[MX - x.w] >= 0) {
  90.                 res = max(res, max(x.mx - x.w, fu[MX - x.w]));
  91.             }
  92.  
  93.             int m = x.w - x.mx;
  94.             x.mx = x.w - x.mn;
  95.             x.mn = m;
  96.  
  97.             if(min(x.mn, x.w + w_root) >= 0 && fd[MX - x.w - w_root] >= 0) {
  98.                 res = max(max(res, fd[MX - x.w - w_root]), max(x.mx, x.w + w_root));
  99.             }
  100.         }
  101.  
  102.         for(node &x : cur) {
  103.             if(x.mn == x.w) {
  104.                 fd[x.w + MX] = max(fd[x.w + MX], x.mx - x.w);
  105.                 tr.eb(x.w + MX);
  106.             }
  107.  
  108.             int m = x.w - x.mx;
  109.             x.mx = x.w - x.mn;
  110.             x.mn = m;
  111.  
  112.             if(min(x.mn, x.w + w[ch[root]]) >= 0) {
  113.                 int id = x.w + w[ch[root]] + MX;
  114.                 fu[id] = max(fu[id], max(x.mx, x.w + w_root));
  115.                 tr.eb(id);
  116.             }
  117.         }
  118.  
  119.         cur.clear();
  120.     }
  121.  
  122.     for(int &i : tr) fd[i] = fu[i] = -1e9;
  123.  
  124.     for(int &v : G[root]) if(!del[v]) {
  125.         solve(v);
  126.     }
  127.  
  128.     return;
  129. }
  130.  
  131. void solve() {
  132.     cin >> n;
  133.     for(int i = 2; i <= n; i++) {
  134.         int p; cin >> p;
  135.         G[p].eb(i);
  136.         G[i].eb(p);
  137.     }
  138.  
  139.     w['('] = 1;
  140.     w[')'] = -1;
  141.  
  142.     for(int i = 1; i <= n; i++) cin >> ch[i];
  143.  
  144.     memset(fu, -63, sizeof fu);
  145.     memset(fd, -63, sizeof fd);
  146.  
  147.     solve(1);
  148.     cout << res;
  149.  
  150.     return;
  151. }
  152.  
  153. int32_t main() {
  154.     ios::sync_with_stdio(false);
  155.     cin.tie(0), cout.tie(0);
  156.     #define task "treeb"
  157.     if(fopen(task".inp", "r")) {
  158.         freopen(task".inp", "r", stdin);
  159.         freopen(task".out", "w", stdout);
  160.     }
  161.  
  162.     int testcase = multi == 2 ? 1e9 : 1; if(multi == 1) cin >> testcase;
  163.     while(testcase--) solve();
  164.     return 0;
  165. }
  166.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FN26A2
language:
C++ (gcc 8.3)
created:
18 hours 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!