标算复杂度似乎是$O(3^{n}*n^2)$的，但可以$O(2^{n}*n^3)$

首先枚举哪些点是叶子。(设枚举的点集为 $s_1$,剩下的点集为 $s_2$)

如何保证一个点 $i$ 是叶子？

只要让 $i$ 往 $s_2$ 连一条边就可以了。

所以方案数 $f[s_1]=$ $s_2$ 的生成树个数 $ \times \prod_{i,i \in s_1}$ $i$ 连向 $s_2$ 的边数。前一项可以用矩阵树求

但这样其实只能保证 ${\textbf s_1}$ 的点是叶子，却不能保证 ${\textbf s_2}$ 的点不是叶子。

现在要求只有 ${\textbf s}$ 的点是叶子的方案数 $ans[s]$，就再容斥一下:

$ ans[s]=\sum_{s',s' \supseteq s } f[s'] * (-1)^{|s'|-|s|} $

这个东西如果暴力的话因为每个点有三种状态所以复杂度$O(3^{n})$

但他其实类似高维前缀和，于是可以$O(2^{n}*n)$

答案就是$\sum_{s,|s|=k} ans[s]$

总复杂度是$\sum_{i=0}^{s} cnt[s-i]^{3}$ , 其中$s=2^{n}-1$,$cnt[s]$ 表示二进制数 $s$ 中 $1$ 的个数

当$n=10$时，这个值为$166400$

但我也不会算，就当它是$O(2^{n}*n^3)$吧

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

template <typename T> void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

struct vec
{
    int *a,n;
    void pb(int x)
    {
        if(n==(n&-n))
        {
            int *_a=new int [n*2];
            memcpy(_a,a,n*sizeof(int));
            a=_a;
        }
        a[n++]=x;
    }
};

const int N=10,U=1<<N;
int lk[N][N];
ll f[U];

int q[N];
ll qa[N][N],*a[N];
ll gauss(int m)
{
    ll ans=1;
    for(int i=0;i<m;++i)
    {
        for(int j=i+1;j<m;++j)
        {
            while(a[j][i])
            {
                ll bi=a[i][i]/a[j][i];
                for(int k=i;k<m;++k)
                 a[i][k]-=a[j][k]*bi;

                swap(a[i],a[j]);
                ans=-ans;
            }
        }
        ans*=a[i][i];
    }
    return ans;
}

int main()
{
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);

    for(int i=0;i<N;++i)a[i]=qa[i];

    int n=read(),m=read(),k=read();
    while(m--)
    {
        int x=read()-1,y=read()-1;
        ++lk[x][y];++lk[y][x];
    }
    int u=(1<<n)-1;
    for(int s=1;s<u;++s)
    {
        ll ans=1;

        m=0;
        for(int i=0;i<n;++i)
        if(!(s&(1<<i))) q[m++]=i;
        for(int i=0;i<n;++i)
        if(s&(1<<i)) 
        {
            int cnt=0;
            for(int j=0;j<m;++j) cnt+=lk[i][q[j]];
            ans*=cnt;
        }

        for(int i=0;i<m;++i)
        for(int j=0;j<m;++j)
         a[i][j]=0;

        for(int i=0;i<m;++i)
        for(int j=0;j<i;++j)
        {
          int w=lk[q[i]][q[j]];
          a[i][i]+=w;
          a[j][j]+=w;
          a[i][j]=a[j][i]=-w;
        }

        ans*=gauss(m-1);

        if((n-m-k)%2==1) f[s]=-ans;
        else f[s]=ans;
    }

    for(int i=0;i<n;++i)
    for(int s=0;s<u;++s)
    if( (s&(1<<i))==0 ) f[s]+=f[s+(1<<i)];

    ll ans=0;
    for(int s=0;s<u;++s)
    {
        int cnt=0;
        for(int i=0;i<n;++i)
        if(s&(1<<i))++cnt;
        if(cnt==k)ans+=f[s];
    }
    cout<<ans;
}

迟了半个小时多才ak。。

我打的dp似乎是O(n^5)的(不过常数挺小的)，应该不是最优的

考虑到距离序列

一定是一段一段的

每段每个点都向上一段连一条边，并可能存在段内互连

用dp[x][y1][y2][n1][n2]表示做到第x个点，上一段有y1个点还能连1条边,y2个点2条，当前段有n1个点1条，n2个点2条。

当y1=y2=0时，考虑把这个点新开一段

枚举他和当前段连的是2条的点还是1条的点

否则把这个点作为当前段

枚举他和上个段连的是2条的点还是1条的点

并枚举他和当前段内的连边

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=52,D=1e9+7,W1=50,W2=50*50,W3=50*50*50,W4=50*50*50*50;
int n;
int d[N];ll c[N][N];
map<int,int>f[N];

int dp(int x,int y1,int y2,int n1,int n2)
{
    if(y1<0||y2<0||n1<0||n2<0)return 0;
    if(x>n) return y1==0&&y2==0&&n1==0&&n2==0;

    int now=y1*W3+y2*W2+n1*W1+n2;
    if(f[x].count(now)) return f[x][now];

    ll ans=0;
    if(y1==0&&y2==0)
    {
        rep(x1,0,1)
        {
           int x2=1-x1;
           ans+=c[n1][x1]*c[n2][x2]%D*dp(x+1,n1-x1+x2,n2-x2,d[x]-x1-x2==1,d[x]-x1-x2==2);
        }
    }
    else
    {
        rep(x1,0,1)
        {
         int x2=1-x1;
        if(y1-x1+x2>=0&&x2<=y2)
        {
           int nd=d[x]-x1-x2;
           rep(nx1,0,nd)
           rep(nx2,0,nd-nx1)
            ans+=c[y1][x1]*c[y2][x2]%D*c[n1][nx1]%D*c[n2][nx2]%D*
            dp(x+1,y1-x1+x2,y2-x2,n1-nx1+nx2+(nd-nx1-nx2==1),
                                  n2-nx2+(nd-nx1-nx2==2));
        }
        }
    }
    return f[x][now]=ans%D;
}

int main()
{
    freopen("1.in","r",stdin);
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",d+i);
    rep(i,0,n)
    {
       c[i][0]=1;    
       rep(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%D;
    }
    printf("%d\n",dp(3,d[1]==2,d[1]==3,d[2]==2,d[2]==3));
}

容易想到二分。
二分一个值w，将与1相连的边全部减去w，之后做mst。
那么w越大，mst选择的与1相连的边的个数(记作num)就越大。
那么二分出使得num=k的w即可。
因为我们保证了结果是原mst-k*w后最小的，
所以也一定保证了原mst最小。

但问题是，对于一个w，num的值是不确定的，因为最小生成树有很多选择。
网上有人说把二分的w改成double即可，我认为这是错的。
double其实没什么意义，由于边权是整数，1.1和1.2做出来的mst一定是一样的。

其实对于一个w，num的值应该是一个区间[l,r]。
我们二分出使得r>=k的最小的w，那么[l,r]一定包含k，因为w-1的r<k，
这时我们再做一遍mst，使得恰好选k条边即可。

#include<bits/stdc++.h>
using std::sort;

const int N=5005,M=100000,U=100001;
int n,m,k,i;
struct edge
{
    int x,y,id,w;
    bool is;
    bool operator <(const edge &i)const
    {
        if(w!=i.w) return w<i.w;
        return is; 
    }
}q[M+3];
int st[N],top;
int f[N];
int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}
int check(int w,bool can)
{
    for(i=1;i<=m;++i) 
    if(q[i].is)q[i].w-=w;

    int ans=0,x,y;
    sort(q+1,q+m+1);
    for(i=1;i<=n;++i) f[i]=i;
    for(top=0,i=1;i<=m;++i)
    {
        x=find(q[i].x);y=find(q[i].y); 
        if(x==y) continue;
        if(!can&&ans+q[i].is>k) continue;
        f[x]=y;
        st[++top]=q[i].id;
        ans+=q[i].is;
    } 

    for(i=1;i<=m;++i)     
    if(q[i].is)q[i].w+=w;

    return ans;
} 

#define mid (l+r>>1)

int main()
{ freopen("1.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].w);q[i].id=i;
        q[i].is=(q[i].x==1)||(q[i].y==1);
    }
    if(check(U,1)<k||check(-U,1)>k||top<n-1) printf("-1\n");
    else
    {
        int l=-U,r=U;
        while(l+1!=r)
        if(check(mid,1)<k) l=mid;
        else r=mid;
        check(r,0);
        printf("%d\n",n-1);
        for(;top;--top) printf("%d ",st[top]);
    }
}

题意:n*m的矩阵，有一些点不能选。k次操作，每次都让一个点变成不可选，每次都问当前可选的最大正方形。n,m,k<=2000

我想到了一个方法。过掉了。

新加的点造成的新的正方形一定过那个点，也就一定过它所在的列。

用第j列更新答案时，从当前答案+1开始从小到大试。 由于答案最多增加n次，所以总的尝试次数是O(N+K)的。 每次检验，我们从上到下枚举区间，用单调队列维护当前两边的最小值，时间是O(N)的。 所以总时间O(N^2+NK)

(看了cf的官方题解，没看懂，但时间是nklogk的)

但如果是求矩形最大面积怎么做呢？！！(或许不可做？)

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

void chmax(int &x,int y)
{
    if(x<y)x=y;
}
#define N 2010
int l[N][N],r[N][N];//水平上延伸的极限点
bool ok[N][N];//可用的点 
int now;
bool open;
int n,m,k,len,i,j;
void dp_lr(int i)//dp第i行的l,r 
{
    for (j=1;j<=m;++j)
    if (ok[i][j])
     l[i][j]=l[i][j-1];
    for (j=m;j;--j)
    if (ok[i][j])
     r[i][j]=r[i][j+1]; 
}

struct queue
{
    int q[N],h[N],head,tail;
    void clear()
    {
       head=1;tail=0;
    }
    void push(int x)
    {
        while (tail>=head&&h[tail]>=x) --tail;
        ++tail;
        q[tail]=i;h[tail]=x;
    }
    int len()
    {
        while (i-q[head]>now) ++head;
        if (h[head]<0) return -N;
        return h[head];
    }
}ql,qr;
void dp_ud(int j)//第j列更新当前答案 
{
    for (;;)
    {
        ql.clear();qr.clear();
        for (i=1;i<=now;++i) 
        {
            ql.push(j-l[i][j]);
            qr.push(r[i][j]-j);
        }
        for (;i<=n;++i)
        {
            ql.push(j-l[i][j]);
            qr.push(r[i][j]-j);
            if (ql.len()+qr.len()>=now) break;
        }
        if (i>n) return ;
        ++now;
    }
}

char ch[N]; 

int o;
struct query
{
    int x,y,ans;
    void init()
    {
        scanf("%d%d",&x,&y);
        ok[x][y]=0;l[x][y]=y+1;r[x][y]=y-1;
    }
    void add()
    {
        ans=now;
        ok[x][y]=1;
        dp_lr(x);
        dp_ud(y);
    }
}p[N];

int main()
{ freopen("1.in","r",stdin);freopen("1.out","w",stdout); 
   while (scanf("%d%d%d",&n,&m,&k)!=EOF)
   {
    int i,j;now=0;
    for (i=1;i<=n;++i)
    {
        scanf("%s",ch+1);
        for (j=1;j<=m;++j) 
        if(ch[j]=='.') ok[i][j]=1;
        else { ok[i][j]=0;l[i][j]=j+1;r[i][j]=j-1; }
    }
    for (i=1;i<=k;++i) p[i].init();

    for (i=1;i<=n;++i) {l[i][0]=1;r[i][m+1]=m;dp_lr(i);}
    for (j=1;j<=m;++j) dp_ud(j);

    for (i=k;i;--i) 
     p[i].add();
    for (i=1;i<=k;++i) printf("%d\n",p[i].ans);
   }
}