麻烦的动态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)<?k+2:a*b;
3.常数优化还可以用const mat &t=...直接引用减少复制常数。
代码：
#include<bits/stdc++.h>
#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=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=1e6+;
const int M=4e6+;
int n;
int b[N][];
int a[N],I;
int ori[N];
ll k;
int hd[N],cnt;
int bian[N][];
struct node{
int nxt,to;
}e[*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 ;
if(a>k+||b>k+) return k+;
return __builtin_clzll(a)+__builtin_clzll(b)<?k+:a*b;
}
ll add(const ll &a,const ll &b){
return a+b>k+?k+:a+b;
}
struct mat{
ll a[][];
void clear(){memset(a,,sizeof a);}
void pre(){a[][]=;a[][]=;a[][]=a[][]=;}
void init(){a[][]=a[][]=a[][]=;a[][]=;}
mat operator *(const mat&b){
mat c;
c.a[][]=add(mul(a[][],b.a[][]),mul(a[][],b.a[][]));
c.a[][]=add(mul(a[][],b.a[][]),mul(a[][],b.a[][]));
c.a[][]=add(mul(a[][],b.a[][]),mul(a[][],b.a[][]));
c.a[][]=add(mul(a[][],b.a[][]),mul(a[][],b.a[][]));
return c;
}
void op(){
cout<<a[][]<<" "<<a[][]<<endl;
cout<<a[][]<<" "<<a[][]<<endl;
}
}st[N],base,nowdp; int dfn[N],top[N],dep[N],son[N],sz[N],fa[N];
int fdfn[N];
int low[N];
int df;
int totson[N];
int num[N];//i is i's fa's num[i] son
int in[N];//0 not 1 yes
ll f[N][]; namespace seg1{//get lian
int tot;
int ls[M],rs[M];
mat data[M];
struct tr1{
int ss,nd;
int rt;
void pushup(int x){
data[x]=data[rs[x]]*data[ls[x]];
}
mat get(){
return data[rt];
}
void build(int &x,int l,int r){
x=++tot;
// cout<<" x "<<x<<" "<<l<<" "<<r<<endl;
if(l==r){
data[x]=st[fdfn[l]];return;
}
build(ls[x],l,mid);build(rs[x],mid+,r);
pushup(x);
}
void chan(int p,ll c0,ll c1){
upda(rt,ss,nd,p,c0,c1);
}
mat que(int L,int R){
return query(rt,ss,nd,L,R);
}
mat query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return data[x];
}
mat ret;
ret.pre();
if(mid<R) ret=ret*query(rs[x],mid+,r,L,R);
if(L<=mid) ret=ret*query(ls[x],l,mid,L,R);
return ret;
}
void upda(int x,int l,int r,int p,ll c0,ll c1){
if(l==r){
data[x].a[][]=c0;
data[x].a[][]=c0;
data[x].a[][]=c1;
return;
}
if(p<=mid) upda(ls[x],l,mid,p,c0,c1);
else upda(rs[x],mid+,r,p,c0,c1);
pushup(x);
}
}; }using seg1::tr1;
tr1 t1[N]; int mem[N];
namespace seg2{//get son
int tot;
int ls[M],rs[M];
ll s0[M],s1[M];
struct tr2{
int sz,rt;
void pushup(int x){
s0[x]=mul(s0[ls[x]],s0[rs[x]]);
s1[x]=mul(s1[ls[x]],s1[rs[x]]);
}
void build(int &x,int l,int r){
x=++tot;
if(l==r){
s0[x]=f[mem[l]][]+f[mem[l]][];
s1[x]=f[mem[l]][];
return;
}
build(ls[x],l,mid);build(rs[x],mid+,r);
pushup(x);
}
void chan(int p,ll c0,ll c1){
upda(rt,,sz,p,c0,c1);
}
void upda(int x,int l,int r,int p,ll c0,ll c1){
if(l==r){
s0[x]=c0;
s1[x]=c1;
return;
}
if(p<=mid) upda(ls[x],l,mid,p,c0,c1);
else upda(rs[x],mid+,r,p,c0,c1);
pushup(x);
}
void spe(int &x){
x=++tot;
s0[x]=;s1[x]=;
}
ll get0(){
return s0[rt];
}
ll get1(){
return s1[rt];
}
}; }using seg2::tr2;
tr2 t2[N]; int sta[N],tp;
void dfs1(int x,int d){
dep[x]=d;
sz[x]=;
if(!in[x])f[x][]=;
else f[x][]=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa[x]) continue;
fa[y]=x;
dfs1(y,x);
sz[x]+=sz[y];
if(sz[y]>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[][]*=(f[y][]);
}else{
st[x].a[][]*=(f[y][]+f[y][]);
st[x].a[][]*=(f[y][]+f[y][]);
}
}
if(in[x]) st[x].a[][]=st[x].a[][]=;
else st[x].a[][]=; 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]<=){//special
t2[x].spe(t2[x].rt);
}
else if(totson[x]>){
int lp=;
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,,lp);
}
}
mat upda(int x){
mat ret;
ret.clear();
while(x){
if(in[x]==){//must not
t1[top[x]].chan(dfn[x],t2[x].get0(),);
}else if(in[x]==){//must yes
t1[top[x]].chan(dfn[x],,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[][],ret.a[][]),ret.a[][]);
}
x=fa[x];
}
return ret;
}
int main(){
rd(n);
scanf("%lld",&k);
base.a[][]=; for(reg i=;i<n;++i) rd(b[i][]),++b[i][];
for(reg i=;i<n;++i) {
rd(b[i][]);
++b[i][];
addedge(b[i][],b[i][]);
addedge(b[i][],b[i][]);
}
rd(I);
for(reg i=;i<=I;++i) rd(a[i]),++a[i],in[a[i]]=,ori[a[i]]=;
sort(a+,a+I+); if(k==){
for(reg i=;i<=I;++i){
printf("%d ",a[i]-);
}
return ;
}
dfs1(,);
dfs2();
//shu lian pou fen int lcp=I;//warning!! numth
ll remain=k;
for(reg i=a[lcp]+;i<=n;++i){
in[i]=;
nowdp=upda(i);
}
ll tot=add(nowdp.a[][],nowdp.a[][]);
int lp=; if(tot-<remain){
remain-=max(1LL*,tot-);
int ptr=a[lcp]-;
for(;lcp;--lcp){
in[a[lcp]]=;
nowdp=upda(a[lcp]);
tot=add(nowdp.a[][],nowdp.a[][]);
if(tot-<remain){
remain-=tot-;
in[a[lcp]]=;
nowdp=upda(a[lcp]);
}else{
break;
}
ptr=a[lcp]-;
while(ptr&&ori[ptr]!=){
in[ptr]=;
nowdp=upda(ptr);
--ptr;
}
}
if(!lcp){
return ;
}
} lp=a[lcp]+;
for(reg i=lp;i<=n;++i){
in[i]=;
nowdp=upda(i);
tot=add(nowdp.a[][],nowdp.a[][]);
if(tot<remain){
remain-=tot;
in[i]=;
nowdp=upda(i);
}else{
--remain;
}
if(remain==) break;
}
for(reg i=;i<=n;++i){
if(in[i]==){
printf("%d ",i-);
}
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/20 11:04:52
*/
字典序处理、轻儿子维护值得注意