Description

BZOJ只是扔了个下载

Solution

设$f[x][i]$表示$x$点选中$i$个黑点的最小连通块。

设$g[x][i]$表示$x$点选中$i$个黑点的最大连通块。

转移非常明显。处理出每个情况的上下界之后差分一下$O(1)$回答询问即可。

卡空间所以要用$short$。 第二次$INF$开大了……应该多上点心了……

Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N (5009)  5 using namespace std; 6  7 struct Edge{
    int to,next;}edge[N<<1]; 8 int n,u,v,T,q,INF=1e4,size[N],b[N]; 9 short f[N][N],g[N][N],tmpf[N],tmpg[N],ans[N][N];10 int head[N],num_edge;11 12 void add(int u,int v)13 {14     edge[++num_edge].to=v;15     edge[num_edge].next=head[u];16     head[u]=num_edge;17 }18 19 void Dfs(int x,int fa)20 {21     size[x]=1;22     for (int i=0; i<=n; ++i)23         f[x][i]=INF,g[x][i]=-INF;24     f[x][b[x]]=g[x][b[x]]=1;25     for (int i=head[x]; i; i=edge[i].next)26         if (edge[i].to!=fa)27         {28             int to=edge[i].to;29             Dfs(to,x);30             for (int j=0; j<=size[x]+size[to]; ++j)31                 tmpf[j]=INF,tmpg[j]=-INF;32             for (int j=0; j<=size[x]; ++j)33                 for (int k=0; k<=size[to]; ++k)34                 {35                     tmpf[j+k]=min((int)tmpf[j+k],(int)f[x][j]+f[to][k]);36                     tmpg[j+k]=max((int)tmpg[j+k],(int)g[x][j]+g[to][k]);37                 }38             size[x]+=size[to];39             for (int j=0; j<=size[x]; ++j)40             {41                 f[x][j]=min(f[x][j],tmpf[j]);42                 g[x][j]=max(g[x][j],tmpg[j]);43             }44         }45     for (int i=0; i<=size[x]; ++i)46         if (f[x][i]