UOJ#387. 【UNR #3】To Do Tree 贪心

刚开始想的贪心是先删掉儿子数量多的.  

但是如果一棵树有一条特别长的链的话这个贪心就假了.   

换一种贪心思路：优先删掉子树深度大的.          

这种贪心题的证明也不会了，感觉没啥反例就当正确了.  

以后做贪心题的时候还是要多手造几组数据，验证正确性.   

code:  

#include <bits/stdc++.h>     
#define N 100009  
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;  
int n,m,edges; 
int dis[N],nex[N],to[N],hd[N]; 
vector<int>G[N];   
struct data { 
    int x,siz;  
    data(int x=0,int siz=0):x(x),siz(siz){}   
    bool operator<(const data b) const {  
        return siz<b.siz;  
    }
};    
priority_queue<data>q;    
vector<int>ans[N];    
void add(int u,int v) {  
    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v; 
}
void dfs(int x,int ff) {  
    dis[x]=0;  
    for(int i=hd[x];i;i=nex[i]) { 
        int y=to[i]; 
        if(y==ff) continue;  
        dfs(y,x);  
        dis[x]=max(dis[x],dis[y]+1); 
    }            
}
int main() {  
    // setIO("input");     
    // freopen("input.out","w",stdout);  
    int x,y,z; 
    scanf("%d%d",&n,&m);    
    for(int i=2;i<=n;++i) {  
        scanf("%d",&x);  
        G[x].push_back(i);     
        add(x,i); 
    }        
    dfs(1,0); 
    q.push(data(1,dis[1]));    
    int re=0; 
    for(int i=1;!q.empty();++i) {          
        for(int j=1;j<=m&&!q.empty();++j) {     
            data e=q.top(); q.pop();   
            ans[i].push_back(e.x);    
        }     
        for(int j=0;j<ans[i].size();++j) {  
            int x=ans[i][j];   
            for(int k=0;k<G[x].size();++k) { 
                q.push(data(G[x][k],dis[G[x][k]]));   
            }
        }   
        re=i;  
    }    
    printf("%d
",re);                   
    for(int i=1;i<=re;++i) { 
        printf("%d ",ans[i].size());  
        for(int j=0;j<ans[i].size();++j) printf("%d ",ans[i][j]);   
        printf("
");  
    }                
    return 0; 
}