fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. using pii = pair<int, int>;
  7. const int N = 1e5 + 5;
  8. int n, k;
  9. bool onColor[N];
  10.  
  11. vector<int> G[N];
  12. int W[N], par[N], h[N], tin[N], tout[N], tour[N], stt = 0, ans = 0, tans = 0, lim = 0;
  13. vector<int> Color[N], Depth[N];
  14. map<int, int> cnt[N];
  15. int cAtDep[N], cc[N];
  16. int vis[N], vers = 0;
  17.  
  18. inline bool ckmax(int &u, int v) {
  19.     if (u < v) return u = v, 1;
  20.     return 0;
  21. }
  22. inline void calcans(int t1, int t2) {
  23.     if (ckmax(ans, t1)) tans = t2;
  24.     else if (ans == t1) tans = min(tans, t2);
  25. }
  26.  
  27. namespace sub1 {
  28. bool checksub() {
  29.     for (int i = 1; i <= n; i++) if ((int)G[i].size() > 1) return false;
  30.     return true;
  31. }
  32. void solve() {
  33.     map<int, int> cnt;
  34.     for (int i = 1; i <= n; i++) cnt[W[i]]++;
  35.     for (pii item: cnt) ans = max(ans, item.sc);
  36.     cout << ans << " 0";
  37. }
  38. };
  39. void gettour(int u) {
  40.     tour[++stt] = u;
  41.     tin[u] = stt;
  42.     for (int v: G[u]) {
  43.         h[v] = h[u] + 1;
  44.         gettour(v);
  45.     }
  46.     tout[u] = stt;
  47.     Depth[h[u]].push_back(tout[u]);
  48.     lim = max(lim, h[u]);
  49. }
  50.  
  51. namespace sub2 {
  52. void dfs(int u, int root) {
  53.     cc[h[u]]++;
  54.     if (W[u] == W[root]) cAtDep[h[u]]++;
  55.     for (int v: G[u]) {
  56.         dfs(v, root);
  57.     }
  58. }
  59. void solve() {
  60.     for (int u = 1; u <= n; u++) {
  61.         dfs(u, u);
  62.         int val = 0, t = 0;
  63.         for (int i = h[u]; i <= lim; i++) {
  64.             int add = 0; if (cnt[i].count(W[u])) add = min(cc[i], cnt[i][W[u]]);
  65.             val += add;
  66.             t += add - cAtDep[i];
  67.             // cerr << val << " " << t << "| " << add << " " << cAtDep[i] << "\n";
  68.             cAtDep[i] = cc[i] = 0;
  69.         }
  70.         calcans(val, t);
  71.     }
  72.     cout << ans << " " << tans;
  73. }
  74. };
  75.  
  76.  
  77. namespace sub3 {
  78. bool checksub() {
  79.     for (int i = 1; i <= n; i++) if (Color[i].size() > 10) return false;
  80.     return true; 
  81. }
  82. int getAtDep(int u, int h) {
  83.     int r = upper_bound(Depth[h].begin(), Depth[h].end(), tout[u]) - Depth[h].begin() - 1;
  84.     int l = lower_bound(Depth[h].begin(), Depth[h].end(), tin[u]) - Depth[h].begin();
  85.     return r - l + 1;
  86. }
  87. void solve() {
  88.     for (int c = 1; c <= k; c++) if (Color[c].size()) {
  89.         for (int u: Color[c]) {
  90.             vers++;
  91.             int val = 0, t = 0;
  92.             for (int v: Color[c]) {
  93.                 if (tin[u] <= tin[v] && tout[v] <= tout[u]) cAtDep[h[v]]++;
  94.             }
  95.             for (int v: Color[c]) if (vis[h[v]] != vers) {
  96.                 int d = h[v];
  97.                 cc[d] = getAtDep(u, d);
  98.                 // cerr << cc[d] << "\n";
  99.                 int add = 0; if (cnt[d].count(c)) add = min(cc[d], cnt[d][c]);
  100.                 val += add;
  101.                 t += add - cAtDep[d];
  102.                 // cerr << val << " " << t << "| " << add << " " << cAtDep[i] << "\n";
  103.  
  104.                 vis[d] = vers;
  105.                 cAtDep[d] = cc[d] = 0;
  106.             }
  107.             calcans(val, t);
  108.         }
  109.     }
  110.     cout << ans << " " << tans;
  111. }
  112. }
  113.  
  114. namespace subfull {
  115. int getAtDep(int u, int h) {
  116.     int r = upper_bound(Depth[h].begin(), Depth[h].end(), tout[u]) - Depth[h].begin() - 1;
  117.     int l = lower_bound(Depth[h].begin(), Depth[h].end(), tin[u]) - Depth[h].begin();
  118.     return r - l + 1;
  119. }
  120.  
  121. void caseLight(int c) {
  122.     for (int u: Color[c]) {
  123.         vers++;
  124.         int val = 0, t = 0;
  125.         for (int v: Color[c]) {
  126.             if (tin[u] <= tin[v] && tout[v] <= tout[u]) cAtDep[h[v]]++;
  127.         }
  128.         for (int v: Color[c]) if (vis[h[v]] != vers) {
  129.             int d = h[v];
  130.             cc[d] = getAtDep(u, d);
  131.             int add = 0; if (cnt[d].count(c)) add = min(cc[d], cnt[d][c]);
  132.             val += add;
  133.             t += add - cAtDep[d];
  134.             // cerr << v << " " << h[v] << "\n";
  135.             vis[d] = vers;
  136.             cAtDep[d] = cc[d] = 0;
  137.         }
  138.         calcans(val, t);
  139.     }
  140. }
  141. void dfs(int u, int root) {
  142.     cc[h[u]]++;
  143.     vis[u] = vers;
  144.     lim = max(lim, h[u]);
  145.     if (W[u] == W[root]) cAtDep[h[u]]++;
  146.     for (int v: G[u]) {
  147.         dfs(v, root);
  148.     }
  149. }
  150. void caseHeavy(int c) {
  151.     vers++;
  152.     for (int i = 1; i <= stt; i++) if (vis[tour[i]] != vers && W[tour[i]] == c) {
  153.  
  154.         int u = tour[i];
  155.         lim = 0;
  156.         // cerr << u << "\n";
  157.         dfs(u, u);
  158.         int val = 0, t = 0;
  159.         for (int i = h[u]; i <= lim; i++) {
  160.             int add = 0; if (cnt[i].count(c)) add = min(cc[i], cnt[i][c]);
  161.             val += add;
  162.             t += add - cAtDep[i];
  163.             cAtDep[i] = cc[i] = 0;
  164.         }
  165.         calcans(val, t);
  166.     }
  167. }
  168. void solve() {
  169.     for (int i = 1; i <= n; i++) if (Color[i].size()) {
  170.         if ((int)Color[i].size() <= sqrt(n)) {
  171.             caseLight(i);
  172.         }
  173.         else {
  174.             caseHeavy(i);
  175.         }
  176.     }
  177.     cout << ans << " " << tans;
  178. }
  179. }
  180.  
  181. signed main() {
  182.     cin.tie(NULL)->sync_with_stdio(false);
  183.     if(ifstream("OFFOFF.inp")) {
  184.         freopen("OFFOFF.inp", "r", stdin);
  185.         freopen("OFFOFF.out", "w", stdout);
  186.     }
  187.     cin >> n;
  188.     k = 0;
  189.     for (int i = 1; i <= n; i++) {
  190.         cin >> W[i];
  191.         if (!onColor[W[i]]) k++;
  192.         onColor[W[i]] = 1;
  193.     }
  194.     for (int v = 2; v <= n; v++) {
  195.         int u; cin >> u;
  196.         par[v] = u;
  197.         G[u].push_back(v);
  198.     }
  199.  
  200.     gettour(1);
  201.     for (int i = 1; i <= n; i++) cnt[h[i]][W[i]]++;
  202.     for (int i = 1; i <= n; i++) Color[W[i]].push_back(i);
  203.  
  204.     // if (sub1::checksub()) return sub1::solve(), 0;
  205.     if (n <= 2000) return sub2::solve(), 0;
  206.     if (sub3::checksub()) return sub3::solve(), 0;
  207.     return subfull::solve(), 0;
  208.     return 0;
  209. }
Success #stdin #stdout 0.01s 17740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/BleZpE
language:
C++14 (gcc 8.3)
created:
14 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!