sicily 1140 国王的遗产

//小号40个WA..目今还不知道旧代码WA哪了。。 //有向树dfs枚举断边(模拟砍不大于m/2节点的树枝) #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int mx = 70000; int n,k,m; int root; int v[mx],nxt[mx],head[mx]; bool w[mx]; int mm = 1,mnn; int res,uuu,www; void add_edge( int uu,int vv ) { v[mm] = vv; nxt[mm] = head[uu]; head[uu] = mm++; } //dfs2 找树枝中最小编号 int dfs2( int u,int no_search ) { int mn = u,k; for( int i = head[u]; i ;i = nxt[i] ) { if( !w[i] || v[i] == no_search ) continue; if( mn > ( k=dfs2(v[i],u) ) ) mn = k; } return mn; } int _mnn[mx]; //dfs也可以找最小编号，用数组存储 dfs2用在一些特殊的地方比较方便 int dfs( int u,int ww,int no_search ) { int num = 1,k; int _mn = u; for( int i = head[u]; i ;i = nxt[i] ) { if( !w[i] || v[i] == no_search ) continue; num += dfs(v[i],i,u); if( _mn > _mnn[v[i]] ) _mn = _mnn[v[i]]; } _mnn[u] = _mn; //以下记录搜索到的状态，res存储最多可以得到多少节点(不大于m/2) int rr = m-num; if( rr == num ) //mid的时候独立处理一下 { int k = dfs2(root,-1); www = ww; //被砍的边 uuu = no_search; //被砍边u res = num; //树枝节点数 if( k == _mn ) mnn = _mn; //mnn是树枝最小编号 else mnn = k; } else if( num <= m/2 ) { if( res <= num ) { if( res == num && _mn > mnn ) return num; www = ww; uuu = no_search; mnn = _mn; res = num; } } else { if( res <= rr ) { int k = dfs2(no_search,u); if( res == rr && k > mnn ) return num; www = ww; uuu = no_search; mnn = k; res = rr; } } return num; } void f() //一个f() 砍一次树 { int mid = m/2; res = 0;mnn = 100000; for( int i = head[root]; i ;i = nxt[i] ) { if( w[i] ) dfs( v[i],i,root ); } printf("%d ",res); m -= res; w[www] = 0; int l = v[www]; //注意同时砍掉反向边 for( int i = head[l]; i ;i = nxt[i] ) { if( v[i] == uuu ) { w[i] = 0;break; } } //root被砍掉就更新root if( dfs2(root,-1) == mnn ) { root = l; } } int main() { //freopen("1.txt","r",stdin); memset( w,true,sizeof(w) ); scanf("%d%d",&n,&k); m = n; int a,b; for( int i = 0;i < n-1;i++ ) { scanf("%d%d",&a,&b); add_edge( b,a ); add_edge( a,b ); } root = 1; while( k-- > 1 ) f(); printf("%d/n",m); return 0; }