Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

#define INF 2000000000000000000

inline int rd()

{

	register int res = 0;register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res;

}

struct myll

{

	long long v;

	inline friend myll operator + (myll a,myll b){return (myll){a.v + b.v > INF ? INF : a.v + b.v};}

	inline friend myll operator * (myll a,myll b)

	{

		if(!a.v || !b.v)return (myll){0};if(a.v == INF || b.v == INF) return (myll){INF}; 

		return (myll){((__builtin_clzll(a.v) + __builtin_clzll(b.v) < 66) ? INF : a.v * b.v)}; 

	}

};

typedef myll ll;

int n;

ll k;

#define MAXN 1000010

int a[MAXN],b[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int I[MAXN];

int son[MAXN],fa[MAXN],dep[MAXN],top[MAXN],bot[MAXN],siz[MAXN];

int deg[MAXN];

int rnk[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;siz[k] = 1;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])son[k] = e[i].to;

		}

	}

	return;

}

int chid[MAXN];

void dfs2(int k,int tp)

{

	top[k] = tp;

	rnk[k] = ++tot;th[tot] = k;

	if(son[k] == 0){bot[k] = k;return;}

	dfs2(son[k],tp);bot[k] = bot[son[k]];

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			chid[e[i].to] = ++deg[k];

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

ll f[MAXN][2];

int tag[MAXN];

namespace T

{

	struct node

	{

		int lc,rc;

		ll mul;

	}t[MAXN << 3];

	int ptr = 0;

	inline int newnode(){return ++ptr;}

	int root[MAXN][2];

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		t[rt].mul = (myll){1};

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void build(int k)

	{

		if(deg[k] == 0)return;

		build(root[k][0],1,deg[k]);

		build(root[k][1],1,deg[k]);

		return;

	}

	void set(int rt,int p,ll v,int l,int r)

	{

		if(l == r){t[rt].mul = v;return;}

		if(p <= mid)set(t[rt].lc,p,v,l,mid);

		else set(t[rt].rc,p,v,mid + 1,r);

		t[rt].mul = t[t[rt].lc].mul * t[t[rt].rc].mul;

		return;

	}

	void set(int k,int son,ll val1,ll val2)

	{//cout << k << " " << son << " : " << val1.v << " " << val2.v << endl;

		if(deg[k] == 0)return;

		set(root[k][0],son,val1,1,deg[k]);

		set(root[k][1],son,val2,1,deg[k]);

		return;

	}

	ll query(int k,int tp)

	{//cout << k << " " << tp << " " << t[root[k][tp]].mul.v << endl;

		if(deg[k] == 0)return (myll){1};

		else return t[root[k][tp]].mul;

	}

}

struct matrix

{

	ll m[2][2];

	matrix(){memset(m,0,sizeof(m));}

	inline friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		c.m[0][0] = a.m[0][0] * b.m[0][0] + a.m[0][1] * b.m[1][0];

		c.m[0][1] = a.m[0][0] * b.m[0][1] + a.m[0][1] * b.m[1][1];

		c.m[1][0] = a.m[1][0] * b.m[0][0] + a.m[1][1] * b.m[1][0];

		c.m[1][1] = a.m[1][0] * b.m[0][1] + a.m[1][1] * b.m[1][1];

		return c;

	}

}m[MAXN];

void dp(int k,int fa)

{

	f[k][0].v = f[k][1].v = 1;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dp(e[i].to,k);

		f[k][1] = f[k][1] * f[son[k]][0];

		f[k][0] = f[k][0] * (f[son[k]][0] + f[son[k]][1]);

		if(e[i].to != son[k])T::set(k,chid[e[i].to],f[e[i].to][0] + f[e[i].to][1],f[e[i].to][0]);

	}

	m[k].m[0][1] = T::query(k,1);m[k].m[1][1].v = 0;

	m[k].m[1][0] = m[k].m[0][0] = T::query(k,0);//cout << T::query(k,0).v << " " << T::query(k,1).v << endl;

	//cout << k << " " << f[k][0].v << " " << f[k][1].v << endl;

	return;

}

struct node

{

	int lc,rc;

	matrix mul;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void maintain(int rt,int p,int l,int r)

{

	if(l == r)

	{

		register int k = th[l];

		m[k].m[0][1] = T::query(k,1);m[k].m[1][1].v = 0;

		m[k].m[1][0] = m[k].m[0][0] = T::query(k,0);

		if(tag[k] == 0)m[k].m[0][1].v = m[k].m[1][1].v = 0;

		if(tag[k] == 1)m[k].m[0][0].v = m[k].m[1][0].v = 0;

		t[rt].mul = m[k];

		return;

	}

	if(p <= mid)maintain(t[rt].lc,p,l,mid);

	else maintain(t[rt].rc,p,mid + 1,r);

	t[rt].mul = t[t[rt].rc].mul * t[t[rt].lc].mul;

	return;

}

matrix query(int rt,int L,int R,int l,int r)

{//cout << l << " " << r << " " << L << " " << R << endl;

	if(L <= l && r <= R)return t[rt].mul;

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

	return query(t[rt].rc,L,R,mid + 1,r) * query(t[rt].lc,L,R,l,mid);

}//bool check = false;

void change(int k,int tp)

{//if(check)cout << k << " -: " << tp << endl;

	if(k == 0)return;

	tag[k] = tp;

	maintain(root,rnk[k],1,n);//query(k,0);if(fa[k] != 0)query(fa[k],0);

	//if(check)cout << m[k].m[0][0].v << " " << m[k].m[0][1].v << " " << m[k].m[1][0].v << " " << m[k].m[1][1].v << endl;

	//if(check)if(fa[k])cout << m[fa[k]].m[0][0].v << " " << m[fa[k]].m[0][1].v << " " << m[fa[k]].m[1][0].v << " " << m[fa[k]].m[1][1].v << endl;

	//if(check)if(fa[k])query(fa[k],0);

	while(top[k] != 1)

	{

		k = top[k];//if(check)cout << k << " -> " << fa[k] << " " << query(k,0).v << " " << query(k,1).v << endl;

		matrix res = query(root,rnk[k],rnk[bot[k]],1,n);

		T::set(fa[k],chid[k],res.m[0][0] + res.m[0][1],res.m[0][0]);

		maintain(root,rnk[fa[k]],1,n);

		k = fa[k];

	}

	return;

}

bool get[MAXN];

inline void write(int x){

	register int y = 10,len = 1;

	while(y <= x){y *= 10;++len;}

	while(len--){y /= 10;putchar(x / y + 48);x %= y;}

	return;

}

int main()

{//freopen("kkk.in","r",stdin);freopen("kkk.out","w",stdout);

//freopen("80.in","r",stdin);freopen("80.out","w",stdout);

	scanf("%d%lld",&n,&k.v);

	for(register int i = 1;i < n;++i)a[i] = rd() + 1;

	for(register int i = 1;i < n;++i)b[i] = rd() + 1;

	for(register int i = 1;i < n;++i)add(a[i],b[i]);

	dfs1(1,1);dfs2(1,1);//cout << "!!!" << endl;

	for(register int i = 1;i <= n;++i)T::build(i);

	scanf("%d",&I[0]);

	for(register int i = 1;i <= I[0];++i)I[i] = rd() + 1;

	for(register int i = 1;i <= n;++i)tag[i] = 2;

	dp(1,0);//cout << "!!!" << endl;

	build(root,1,n);//cout << "###" << endl;

	for(register int i = 1;i <= n;++i)maintain(root,rnk[i],1,n);//cout << "$$$" << endl;

	//for(int i = 1;i <= n;++i)cout << i << " : " << (query(i,0) + query(i,1)).v << endl;

	sort(I + 1,I + 1 + I[0]);

	for(register int i = 1;i <= I[0];++i)

	{

		for(register int j = (i == 1 ? 0 : I[i - 1]) + 1;j < I[i];++j)change(j,0);

		change(I[i],1);

	}

	register int lcp = I[0];I[I[0] + 1] = n + 1;

	for(register int i = I[I[0]] + 1;i <= n;++i)change(i,2);//cout << "!!!" << endl;

	for(register int i = I[0];i >= 0;--i)

	{

		matrix res = query(root,rnk[1],rnk[bot[1]],1,n);

		ll val;val.v = res.m[0][0].v + res.m[0][1].v - 1;//cout << val.v << endl;

		if(val.v < k.v)k.v -= val.v;else{lcp = i;break;}

		if(i == 0)return 0;

		change(I[i],0);

		if(i != I[0])for(int p = I[i] + 1;p <= I[i + 1];++p)change(p,2);

	}

	//cout << lcp << endl;

	//cout << "!!!" << endl;

	for(register int i = 1;i <= lcp;++i)get[I[i]] = true;

	I[I[0] + 1] = I[I[0]];

	for(register int i = I[lcp + 1] + 1;i <= n;++i)

	{//cout << i << endl;

		change(i,1);//cout << "###" << endl;

		matrix res = query(root,rnk[1],rnk[bot[1]],1,n);

		ll val = res.m[0][0] + res.m[0][1];//cout << val << endl;

		if(val.v < k.v)get[i] = false,k.v -= val.v,change(i,0);

		else get[i] = true,k.v -= 1;

		if(k.v == 0)break;

	}

	for(register int i = 1;i <= n;++i)if(get[i])write(i - 1),putchar(' '); 

	cout << endl;

	return 0;

}