daily 2

CF 777E
典中典 优先队列的状态选择问题，典行的dp

struct node{
    int a,b,h;
    bool operator <(const node& aa)const{
        if(b==aa.b){
            return a>aa.a;
        }
        return b>aa.b;
    }
};
struct sta{
    int w,h;
    bool operator <(const sta& a)const{
        return h<a.h;//p should use opposite
    }
};
void solve(){
  int n;
  cin>>n;
  vector<node>arr(n+1);
  for(int i=1;i<=n;++i)cin>>arr[i].a>>arr[i].b>>arr[i].h;
  sort(arr.begin()+1,arr.end());
  priority_queue<sta>q;
  q.push({0,0});
  int ans=-1;
  for(int i=1;i<=n;++i){
    while(q.top().w>=arr[i].b){
        q.pop();
    }
    ans=max(ans,q.top().h+arr[i].h);
    q.push({arr[i].a,q.top().h+arr[i].h});
  }
  cout<<ans<<'\n';
  return;
}

CF 796C

看题解做的，还是有点不太理解

总之答案共有三种 max+1,max,max+2(这个不难理解)

什么时候为max？就是只有一个点为max，且剩下的max-1都在一个点的邻居里

什么时候为max+1?就是所有的max的点都可以在一个点的子树里

剩下的时候都是max+2

void solve(){
  int n;
  cin>>n;
  vector<int>a(n+1);
  int max_=-INF;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    max_=max(a[i],max_);
  }
  vector<vector<int>>E(n+1);
  for(int i=1;i<=n-1;++i){
    int u,v;
    cin>>u>>v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  vector<pii>info(n+1);
  int max_cnt=0,max_minus_cnt=0;
  for(int i=1;i<=n;++i){
    if(a[i]==max_){
        ++max_cnt;
    }
    if(a[i]==max_-1){
        ++max_minus_cnt;
    }
  }
  for(int i=1;i<=n;++i){
    int m_c=0,m1_c=0;
    if(a[i]==max_){
        ++m_c;
    }if(a[i]==max_-1){
        ++m1_c;
    }
    for(int v:E[i]){
        if(a[v]==max_){
            ++m_c;
        }
        if(a[v]==max_-1){
            ++m1_c;
        }
    }
    info[i]=make_pair(m_c,m1_c);
  }
  int r;
  for(int i=1;i<=n;++i){
    if(a[i]==max_){
        r=i;
        break;
    }
  }
  if(max_cnt==1){
    if(info[r].second==max_minus_cnt){
        cout<<max_<<'\n';
        return;
    }
  }
  for(int i=1;i<=n;++i){
    if(info[i].first==max_cnt){
        cout<<max_+1;
        return;
    }
  }
  cout<<max_+2<<'\n';
  return;
}