c/c++语言开发共享BZOJ4919: [Lydsy1706月赛]大根堆(set启发式合并)

#include<bits/stdc++.h>  #define sit multiset<int>::iterator   using namespace std;  const int maxn = 2e5 + 10;  inline int read() {      char c = getchar(); int x = 0, f = 1;      while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}      while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();      return x * f;  }  vector<int> v[maxn];  multiset<int> s[maxn];  int n, val[maxn];  void dfs(int x, int fa) {      for(int i = 0; i < v[x].size(); i++) {          int to = v[x][i];          if(to == fa) continue;          dfs(to, x);          if(s[to].size() > s[x].size()) swap(s[to], s[x]);          for(sit it = s[to].begin(); it != s[to].end(); it++)              s[x].insert(*it);          s[to].clear();      }      sit it = s[x].lower_bound(val[x]);      if(it != s[x].end()) s[x].erase(it);      s[x].insert(val[x]);  }  main() {      n = read();      for(int i = 1; i <= n; i++) {          val[i] = read();          int x = read();          v[i].push_back(x); v[x].push_back(i);      }      dfs(1, 0);      printf("%d", s[1].size());      return 0;  }