fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int,int>
  13. #define pli pair<ll,int>
  14. #define vi vector<int>
  15.  
  16. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef unsigned int ui;
  22.  
  23. using namespace std;
  24.  
  25. const int M = 1e9 + 7;
  26. const int INF = 1e9 + 7;
  27. const ll INFLL = (ll)2e18 + 7LL;
  28. const ld PI = acos(-1);
  29.  
  30. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  31. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  32.  
  33. template<class _, class __>
  34.     bool minimize(_ &x, const __ y){
  35.         if(x > y){
  36.             x = y;
  37.             return true;
  38.         } else return false;
  39.     }
  40. template<class _, class __>
  41.     bool maximize(_ &x, const __ y){
  42.         if(x < y){
  43.             x = y;
  44.             return true;
  45.         } else return false;
  46.     }
  47.  
  48. template<class _,class __>
  49.     void Add(_ &x, const __ y) {
  50.         x += y;
  51.         if (x >= M) {
  52.             x -= M;
  53.         }
  54.         return;
  55.     }
  56.  
  57. template<class _,class __>
  58.     void Diff(_ &x, const __ y) {
  59.         x -= y;
  60.         if (x < 0) {
  61.             x += M;
  62.         }
  63.         return;
  64.     }
  65.  
  66. //--------------------------------------------------------------
  67.  
  68. const int MaxN = 2e5+7;
  69.  
  70. int n,q,a[MaxN],p[MaxN],sz[MaxN],res[MaxN];
  71. vi adj[MaxN];
  72. multiset<int> f[MaxN];
  73.  
  74. void dfs1(int u) {
  75.     sz[u] = 1;
  76.     for (int v : adj[u]) {
  77.         dfs1(v);
  78.         sz[v] += sz[u];
  79.     }
  80. }
  81.  
  82. void dfs(int u) {
  83.     int nxt = 0;
  84.     for (int v : adj[u]) {
  85.         if (sz[v] > sz[nxt]) nxt = v;
  86.     }
  87.     if (nxt != 0) {
  88.         dfs(nxt);
  89.         swap(f[u],f[nxt]);
  90.     }
  91.     for (int v : adj[u]) {
  92.         if (v == nxt) continue;
  93.         dfs(v);
  94.         for (multiset<int>::iterator it = f[v].begin();it!=f[v].end();it++) {
  95.             f[u].insert(*it);
  96.         }
  97.         f[v].clear();
  98.     }
  99.     multiset<int>::iterator it = f[u].lower_bound(a[u]);
  100.     if (it == f[u].end()) {
  101.         f[u].insert(a[u]);
  102.     }
  103.     else {
  104.         multiset<int>::iterator it1 = f[u].upper_bound(a[u]);
  105.         if (it1 == it) {
  106.             f[u].erase(it);
  107.             f[u].insert(a[u]);
  108.         }
  109.     }
  110.     res[u] = f[u].size();
  111. }
  112.  
  113. void sol() {
  114.     cin >> n >> q;
  115.     for (int i=1;i<=n;i++) cin >> a[i];
  116.     for (int i=2;i<=n;i++) {
  117.         cin >> p[i];
  118.         adj[p[i]].pb(i);
  119.     }
  120.     dfs1(1);
  121.     dfs(1);
  122.     for (int i=1;i<=q;i++) {
  123.         int u;
  124.         cin >> u;
  125.         cout << res[u] << '\n';
  126.     }
  127. }
  128.  
  129. int main() {
  130. //	freopen("test.inp","r",stdin);
  131. //	freopen("test.out","w",stdout);
  132. 	FAST
  133. 	int t=1;
  134. //	cin >> t;
  135. 	while (t--) sol();
  136. }
  137.  
Success #stdin #stdout 0.01s 19188KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/chbPWT
language:
C++14 (gcc 8.3)
created:
6 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!