对于一棵树和一个给出的独立集S，设S的字典序排名为x，求这棵树字典序第x+k大的独立集

因为要求字典序第x+k大，x可能非常大，所以我们要逐位枚举确定这个独立集
我们先枚举确定答案独立集和S的LCP，然后从LCP开始再按编号往大枚举每个点是否在独立集中
这需要我们资瓷一个操作：对一个点，要求他一定在/不在独立集中，求整棵树的独立集个数，注意这个操作是持久化的，即对后面的操作也有影响

这是（非常自然的？）动态dp…
对于我们求独立集个数的过程，对于树上的每个点，他有三种状态，选，不选，可选可不选，对于每种状态我们都可以设计一个关于独立集dp的转移矩阵，将树剖成重链树，一个点所有轻孩子的矩阵和自己的矩阵视为这个点的输入，对于一条重链上我们可以用矩乘优化这个转移，那么每次我们更改一个点的状态，其到根路径上至多经过log条重链，所以我们每次更改一个点的状态后，可以在$log^2m^3$的复杂度内求出这棵树的独立集个数（m是矩阵大小）

总的复杂度大概是$O(nlog^2m^3)$的
实现上有不少细节，比如个数如果超过了k，取k+1就好了，比如乘起来爆longlong要用除法判一下，我的代码一开始用的是除法，后来因为我要卡常，就抄了标算的一个不知道啥东西判qaq

另外这个复杂度跑1e6，对于我这种选手是非常难受的qaq
所以要优化一下常数
比如对于每一条重链单独开一棵线段树，这样可以把一个log优化到很小
一般来说这么改也够了，但是我还是T
我就抄了标算的那个判乘积爆longlong的东西
然后我还是T….
我就循环展开了矩乘，然后过了…（展开后跑的飞快呀虽然还是垫底…）

讲的好像不清不楚呀…

code：

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;inline void read(int &x)
{char c; while(!((c=getchar())>='0'&&c<='9'));x=c-'0';while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
int tpc[10],tn;
const int maxn = 1100000;
const int maxp = maxn<<2;
const ll inf = 1e18+maxn;
inline void add(ll &a,const ll &b)
{a+=b;if(a>inf) a=inf;
}
inline ll mul(ll a,ll b)
{if(!a||!b) return 0;if(a==inf||b==inf) return inf;return __builtin_clzll(a)+__builtin_clzll(b)<66?inf:a*b; 
}int n; ll K;
int ei[maxn],s[maxn],sn;
struct edge{int y,nex;}a[maxn<<1]; int len,fir[maxn];
inline void ins(const int x,const int y){a[++len]=(edge){y,fir[x]};fir[x]=len;}
int siz[maxn],son[maxn],fa[maxn],top[maxn],w[maxn],R[maxn];
int L[maxn],fi[maxn];
void dfs(const int x)
{siz[x]=1;for(int k=fir[x],y=a[k].y;k;k=a[k].nex,y=a[k].y) if(y!=fa[x]) fi[y]=++L[x];for(int k=fir[x],y=a[k].y;k;k=a[k].nex,y=a[k].y) if(y!=fa[x]){fa[y]=x;dfs(y); siz[x]+=siz[y];if(siz[son[x]]<=siz[y]) son[x]=y;}
}
void build(const int x,const int tp)
{top[x]=tp; w[x]=++R[tp];if(son[x]) build(son[x],tp);for(int k=fir[x],y=a[k].y;k;k=a[k].nex,y=a[k].y) if(y!=fa[x]&&y!=son[x])build(y,y);
}struct mat
{ll a[2][2];mat(){memset(a,0,sizeof a);}friend inline mat operator *(const mat &x,const mat &y){mat re;for(int i=0;i<2;i++){re.a[i][0]=mul(x.a[i][0],y.a[0][0]);add(re.a[i][0],mul(x.a[i][1],y.a[1][0]));re.a[i][1]=mul(x.a[i][0],y.a[0][1]);add(re.a[i][1],mul(x.a[i][1],y.a[1][1]));}return re;}
}one,zero,point,c;
struct segment
{mat seg[maxp];int root[maxn],lc[maxp],rc[maxp],cnt;int loc,lx,rx;void upd(int &x,const int l,const int r){if(!x) x=++cnt;if(l==r) { seg[x]=c; return; }int mid=l+r>>1;if(loc<=mid) upd(lc[x],l,mid);else upd(rc[x],mid+1,r);seg[x]=seg[rc[x]]*seg[lc[x]];}
}seg;
struct Seg
{ll seg[maxp],seg2[maxp];int root[maxn],lc[maxp],rc[maxp],cnt;int loc,lx,rx; ll c,c2;void upd(int &x,const int l,const int r){if(!x) x=++cnt;if(l==r) { seg[x]=c;seg2[x]=c2; return; }int mid=l+r>>1;if(loc<=mid) upd(lc[x],l,mid);else upd(rc[x],mid+1,r);seg[x]=mul(seg[lc[x]],seg[rc[x]]);seg2[x]=mul(seg2[lc[x]],seg2[rc[x]]);}void query(const int x,const int l,const int r,ll &a1,ll &a2){if(rx<l||r<lx) return ;if(lx<=l&&r<=rx) { a1=mul(a1,seg[x]),a2=mul(a2,seg2[x]); return; }int mid=l+r>>1;query(lc[x],l,mid,a1,a2);query(rc[x],mid+1,r,a1,a2);return;}void q1(int x,int d1,ll &a1,ll &a2){ll t1=1,t2=1;lx=1,rx=d1-1; if(lx<=rx) query(root[x],1,L[x],t1,t2);lx=d1+1,rx=L[x]; if(lx<=rx) query(root[x],1,L[x],a1,a2);a1=mul(a1,t1),a2=mul(a2,t2);return;}
}seg2;ll dp[maxn][2],temp[2];
void clear(const int x)
{dp[x][0]=dp[x][1]=1;for(int k=fir[x],y=a[k].y;k;k=a[k].nex,y=a[k].y) if(y!=fa[x]) {clear(y);dp[x][0]=mul(dp[x][0],dp[y][1]);dp[x][1]=mul(dp[x][1],dp[y][0]);}add(dp[x][1],dp[x][0]);seg2.loc=fi[x],seg2.c=dp[x][0],seg2.c2=dp[x][1],seg2.upd(seg2.root[fa[x]],1,L[fa[x]]);temp[0]=temp[1]=1;for(int k=fir[x],y=a[k].y;k;k=a[k].nex,y=a[k].y) if(y!=fa[x]&&y!=son[x]){temp[0]=mul(temp[0],dp[y][0]);temp[1]=mul(temp[1],dp[y][1]);}c.a[1][1]=0;c.a[0][0]=c.a[1][0]=temp[1];c.a[0][1]=temp[0];seg.loc=w[x]; seg.upd(seg.root[top[x]],1,R[top[x]]);
}
int state[maxn];
ll lock(int x,int st)
{state[x]=st;    while(x){int ff=top[x];ll t0=1,t1=1;if(L[x]>1) seg2.q1(x,fi[son[x]],t0,t1);c.a[1][1]=0;c.a[0][0]=c.a[1][0]=t1;c.a[0][1]=t0;if(state[x]==0) c.a[0][1]=0;if(state[x]==1) c.a[0][0]=c.a[1][0]=0;seg.loc=w[x]; seg.upd(seg.root[ff],1,R[ff]);c=seg.seg[seg.root[ff]];add(c.a[0][1],c.a[0][0]);x=ff,ff=fa[x];seg2.loc=fi[x],seg2.c=c.a[0][0],seg2.c2=c.a[0][1],seg2.upd(seg2.root[ff],1,L[ff]);x=ff;}return seg2.c2;
}int main()
{//freopen("tmp.in","r",stdin);//freopen("tmp.out","w",stdout);one.a[0][0]=one.a[1][1]=1;point.a[0][0]=point.a[0][1]=point.a[1][0]=1;read(n); scanf("%lld",&K);for(int i=1;i<n;i++) read(ei[i]);for(int i=1;i<n;i++){int x=ei[i],y; read(y); x++,y++;ins(x,y),ins(y,x);}read(sn);for(int i=1;i<=sn;i++) read(s[i]),s[i]++;sort(s+1,s+sn+1);L[0]=fi[1]=1; dfs(1); build(1,1);clear(1);for(int i=1;i<=n;i++) state[i]=2;int ii=1;for(int i=1;i<s[sn];i++){if(i==s[ii]) ii++,lock(i,1);else lock(i,0);}ll la=lock(s[sn],1);ii=sn;while(la<=K&&ii>0){K++; K-=la; la=lock(s[ii],0);if(ii<sn){for(int j=s[ii]+1;j<=s[ii+1];j++) la=lock(j,2);}ii--;}if(ii==0&&la<K) return 0;int ev=0;for(int i=ii==sn?s[sn]+1:s[ii+1]+1;i<=n;i++){if(ev){if(K==1) break;K--;}la=lock(i,1);if(la<K) {K-=la,la=lock(i,0);if(ev&&la>0) la--;if(ev) K++;}else ev=1;}for(int i=1;i<=n;i++) if(state[i]==1) printf("%d ",i-1);return 0;
}