洛谷4577 & LOJ2521：[FJOI2018]领导集团问题—

洛谷4577 & LOJ2521：[FJOI2018]领导集团问题——题解

阅读量：6203 次

发布时间：2019-06-21

本文共 1692 字，大约阅读时间需要 5 分钟。

参考：

自己再说下另一种理解方法吧。

我们设f[i][j]为i的子树下找到的点集最小值为j的大小。

但不是很好统计，所以我们开f[i][j]表示j~INF的和即为原来的含义。

则我们合并其子树的时候，考虑加入i的w[i]时，其答案f[i][w[i]]还是没有问题的，但是对于比w[i]小的值就全大1了，所以我们找到第一个比w[i]小的w，将其--，之后统计即可。

（当然如果没有比其小的w，我们当然就不需要减啦！）

复杂度O(nlog^2n)只要评测机好点就能过。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;const int N=2e5+5;#define fi first#define se secondinline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int to,nxt;}e[N];int n,m,cnt,head[N],w[N],b[N];map
                
                 f[N];map
                 
                  ::iterator it;inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}inline void merge(int u,int v){ if(f[u].size()
                  
                   fi]+=it->se; } f[v].clear();}void dfs(int u){ for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; dfs(v); merge(u,v); } it=f[u].begin(); if(it->fi>=w[u])return; it=f[u].lower_bound(w[u]);it--; if(it->se==1)f[u].erase(it); else it->se-=1;}inline void LSH(){ sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1; for(int i=1;i<=n;i++) w[i]=lower_bound(b+1,b+m+1,w[i])-b;}int main(){ n=read(); for(int i=1;i<=n;i++)w[i]=b[++m]=read(); LSH(); for(int i=1;i<=n;i++)f[i][w[i]]=1; for(int v=2;v<=n;v++){ int u=read();add(u,v); } dfs(1); int ans=0; for(it=f[1].begin();it!=f[1].end();it++)ans+=it->se; printf("%d\n",ans); return 0;}