#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #define LL long long #define USLL unsigned long long using namespace std; const int MAXN=1e5+5,MAXM=2e4+5; LL dp[25][MAXM]; int W[MAXN],V[MAXN],w[MAXN],v[MAXN],siz[MAXN],dfn[MAXN]; int dp2[MAXM]; int N,M,T; int tim=0; vector<int>gra[MAXN]; int pos[MAXN]; USLL ans1[MAXN],ans2[MAXN]; void dfs(int u) { dfn[u]=++tim; pos[tim]=u; siz[u]=1; for(int v:gra[u]) { dfs(v); siz[u]+=siz[v]; } return; } void DC(int l,int r,vector<int>ve,int dep) { if(l>r) return; if(ve.size()==0) return; if(l==r) { int x=ve[0]; for(int i=0;i<=M;i++) { ans1[x]^=(USLL)dp[dep][i]*(USLL)(i+1); ans2[x]^=(USLL)dp[dep][i]*(USLL)(i+1)*(USLL)(i+1)*(USLL)(i+1); // printf("%d %d %d %lld\n",l,r,x,dp[dep][i]); } //if(x==3) ans1[x]=114514; return; } int mid=(l+r)>>1; for(int i=0;i<=M;i++) dp[dep+1][i]=dp[dep][i]; for(int i=mid+1;i<=r;i++) for(int j=M;j>=w[i];j--) dp[dep+1][j]=max(dp[dep+1][j],dp[dep+1][j-w[i]]+v[i]); vector<int>nxv; for(int u:ve) if(dfn[u]+siz[u]-1<=mid) nxv.push_back(u); DC(l,mid,nxv,dep+1); for(int i=0;i<=M;i++) dp[dep+1][i]=dp[dep][i]; for(int i=l;i<=mid;i++) for(int j=M;j>=w[i];j--) { //printf("%d %d %d %d\n",i,j,w[i],v[i]); dp[dep+1][j]=max(dp[dep+1][j],dp[dep+1][j-w[i]]+v[i]); } //for(int i=0;i<=M;i++) printf("%d\n",dp[dep+1][i]); nxv.clear(); for(int u:ve) if(dfn[u]>mid) nxv.push_back(u); DC(mid+1,r,nxv,dep+1); for(int i=0;i<=M;i++) dp[dep+1][i]=dp[dep][i]; for(int i=0;i<=M;i++) dp2[i]=dp[dep][i]; int q=r; for(int p=l;p<=mid;p++) { if(!pos[p]||p+siz[pos[p]]-1<=mid) { // printf("BACKPACK %d\n",p); for(int j=M;j>=w[p];j--) dp[dep][j]=max(dp[dep][j],dp[dep][j-w[p]]+v[p]); // for(int j=0;j<=M;j++) printf("(%d %lld)",j,dp[dep][j]); // puts(""); continue; } while(q>p+siz[pos[p]]-1) { for(int j=M;j>=w[q];j--) dp[dep][j]=max(dp[dep][j],dp[dep][j-w[q]]+v[q]); q--; } int x=pos[p]; for(int i=0;i<=M;i++) { ans1[x]^=(USLL)dp[dep][i]*(USLL)(i+1); ans2[x]^=(USLL)dp[dep][i]*(USLL)(i+1)*(USLL)(i+1)*(USLL)(i+1); // printf("%d %d %d %d %d %d %lld\n",l,r,x,p,q,i,dp[dep][i]); } //if(x==3) ans1[x]=114514; // printf("BACKPACK %d\n",p); // for(int j=0;j<=M;j++) printf("(%d %lld)",j,dp[dep][j]); for(int j=M;j>=w[p];j--) dp[dep][j]=max(dp[dep][j],dp[dep][j-w[p]]+v[p]); // puts(""); } for(int i=0;i<=M;i++) dp[dep][i]=dp2[i]; return; } int main() { scanf("%d %d %d",&N,&M,&T); for(int i=1;i<=N;i++) scanf("%d",&W[i]); for(int i=1;i<=N;i++) scanf("%d",&V[i]); for(int i=2;i<=N;i++) { int u; scanf("%d",&u); gra[u].push_back(i); } dfs(1); for(int i=1;i<=N;i++) w[dfn[i]]=W[i],v[dfn[i]]=V[i]; // for(int i=1;i<=N;i++) printf("(%d %lld %lld)\n",i,w[i],v[i]); vector<int>vec; for(int i=2;i<=N;i++) vec.push_back(i); DC(1,N,vec,1); for(int i=2;i<=N;i++) printf("%llu %llu\n",ans1[i],ans2[i]); return 0; }