麻烦的动态DP写了2天

简化题意：给树，求比给定独立集字典序大k的独立集是哪一个

 

主要思路：

k排名都是类似二分的按位确定过程。

字典序比较本质是LCP下一位，故枚举LCP，看多出来了多少个独立集，然后判断；枚举完LCP，再往回做过去。

 

外面：

假如是一串0101010表示每个点有没有在独立集里，然后比较这个01串的字典序？

枚举LCP，LCP下一位：原来是0，这次就是1；原来是1，这次必须还是1。后面的随便选择。找方案数

 

但是这里是一般的字典序，两个1中间的0都会省略，使得大小比较没有那么容易

但是也有字典序按位比较的方法（2随便选）

写成01序列00001010100001001010000

首先，最后的0000先都变成2222，找方案数，（因为后面再放上一个1，由于长度更长，所以字典序还是大的。如果原来序列后面有1就不行了（也是为什么下面要跳过中间的0））

不够，每次找最后一个1，变成0，后面都是2，找方案数

两个1中间的0都变成2，这些0变成1的话，直接就比原来的字典序小了。

注意，每一次会有一个后面全是00000的，特殊-1 

 

最后如果剩下lcp是0，就S=∅ return 0

 

否则往回找，开始从(1,0)或者(1,1)后面第一个(0,0)开始找（后面的暂时还是2）

大概就是两种情况都是从红色箭头开始

先填1,（因为1小），如果方案大于等于remain，就把1放这儿，remain-=1（因为后面都填0也是一种方案了）

如果小于remain，减掉这次的方案数，然后放0

当途中remain==0，一定是k从1到0，直接break掉

 

最后in[x]=1的就是最终独立集了。

 

动态DP：

统计独立集方案数，f[x][0],f[x][1]表示方案数即可

方案数大于k，和k+2取min

取min了，修改轻儿子不能直接把轻儿子贡献除去，线段树维护轻儿子的f[x][0]+f[x][1]和f[x][0]

每个重链开一个线段树

 

注意：

1.重链在top建立，直接不断找重儿子即可

2.判乘法>k，会爆long long，用long double会被卡常，所以

return __builtin_clzll(a)+__builtin_clzll(b)<66?k+2:a*b;

3.常数优化还可以用const mat &t=...直接引用减少复制常数。

 

代码：

#include
     
      #define reg register int#define il inline#define mid ((l+r)>>1)#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=1e6+6;const int M=4e6+5;int n;int b[N][2];int a[N],I;int ori[N];ll k;int hd[N],cnt;int bian[N][2];struct node{    int nxt,to;}e[2*N];void addedge(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}ll mul(const ll &a,const ll &b){    if(!a||!b) return 0;    if(a>k+1||b>k+1) return k+2;    return __builtin_clzll(a)+__builtin_clzll(b)<66?k+2:a*b;}ll add(const ll &a,const ll &b){    return a+b>k+1?k+2:a+b;}struct mat{    ll a[2][2];    void clear(){memset(a,0,sizeof a);}    void pre(){a[0][0]=1;a[1][1]=1;a[0][1]=a[1][0]=0;}    void init(){a[0][0]=a[1][0]=a[0][1]=1;a[1][1]=0;}    mat operator *(const mat&b){        mat c;        c.a[0][0]=add(mul(a[0][0],b.a[0][0]),mul(a[0][1],b.a[1][0]));        c.a[0][1]=add(mul(a[0][0],b.a[0][1]),mul(a[0][1],b.a[1][1]));        c.a[1][0]=add(mul(a[1][0],b.a[0][0]),mul(a[1][1],b.a[1][0]));        c.a[1][1]=add(mul(a[1][0],b.a[0][1]),mul(a[1][1],b.a[1][1]));        return c;    }    void op(){        cout<
      
       <<" "<
       
        <
        
         sz[son[x]]) son[x]=y;    }}void dfs2(int x){    dfn[x]=++df;    sta[++tp]=x;    fdfn[df]=x;    if(!top[x]) top[x]=x;    if(son[x]) top[son[x]]=top[x],++totson[x],dfs2(son[x]);    st[x].init();        for(reg i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(y==son[x]) continue;        if(y==fa[x]) continue;        num[y]=totson[x];        ++totson[x];        dfs2(y);        if(in[x]){            st[x].a[0][1]*=(f[y][0]);        }else{            st[x].a[0][0]*=(f[y][0]+f[y][1]);            st[x].a[1][0]*=(f[y][0]+f[y][1]);        }    }    if(in[x]) st[x].a[0][0]=st[x].a[1][0]=0;    else st[x].a[0][1]=0;        if(top[x]==x){            t1[x].ss=dfn[x];        t1[x].nd=dfn[sta[tp]];        t1[x].build(t1[x].rt,t1[x].ss,t1[x].nd);        int z;        do{            z=sta[tp];            --tp;        }while(z!=x);    }    if(totson[x]<=1){
   //special         t2[x].spe(t2[x].rt);        }    else if(totson[x]>1){        int lp=0;        for(reg i=hd[x];i;i=e[i].nxt){            int y=e[i].to;            if(y==fa[x]||y==son[x]) continue;            mem[++lp]=y;        }        t2[x].sz=lp;        t2[x].build(t2[x].rt,1,lp);    }}mat upda(int x){    mat ret;    ret.clear();    while(x){        if(in[x]==0){
   //must not            t1[top[x]].chan(dfn[x],t2[x].get0(),0);        }else if(in[x]==1){
   //must yes            t1[top[x]].chan(dfn[x],0,t2[x].get1());        }else{
   //either            t1[top[x]].chan(dfn[x],t2[x].get0(),t2[x].get1());        }        ret=base*t1[top[x]].get();        x=top[x];        if(fa[x]){            t2[fa[x]].chan(num[x],add(ret.a[0][0],ret.a[0][1]),ret.a[0][0]);        }        x=fa[x];    }    return ret;}int main(){    rd(n);    scanf("%lld",&k);    base.a[0][0]=1;        for(reg i=1;i
        
       
      
     

字典序处理、轻儿子维护值得注意