#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; #define int long long const int MAXN=100010,N=20010; struct Edge{int v,nx;}edge[MAXN];int h[MAXN],CNT;void init(){memset(h,-1,sizeof(h));CNT=0;}; void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;} int n,m,T,w[MAXN],v[MAXN],cnt,d[MAXN],s[MAXN],o[MAXN]; void dfn(int now){ d[now]=++cnt;o[cnt]=now; for(int i=h[now];i!=-1;i=edge[i].nx){ dfn(edge[i].v); } s[now]=cnt; } struct asking{ int id,l,r; }q[MAXN],nq[MAXN],tl[MAXN],tr[MAXN]; bool cmp(asking x,asking y){if(x.l!=y.l)return x.l<y.l;else return x.r>y.r;} unsigned long long f[20][N],dp[2][20][N]; unsigned long long as1[MAXN],as3[MAXN]; void fz(int l,int r,int ql,int qr,int tp,int lr){ // cout<<l<<" "<<r<<" "<<lr<<":"<<endl; int cn=0,cl=0,cr=0; int mid=(l+r)>>1; for(int i=ql;i<=qr;i++){ if(q[i].r>mid&&q[i].l>mid){ tr[++cr]=q[i]; } else if(q[i].l<mid&&q[i].r<=mid){ tl[++cl]=q[i]; } else{ nq[++cn]=q[i]; } } if(lr!=2)for(int i=1;i<=m;i++){ f[tp][i]=dp[lr][tp-1][i]; } int ln=l,rn=r; for(int i=1;i<=cn;i++){ while(ln<nq[i].l){ for(int j=m;j>=v[o[ln]];j--){ f[tp][j]=max(f[tp][j],f[tp][j-v[o[ln]]]+w[o[ln]]); } ln++; } while(rn>nq[i].r){ for(int j=m;j>=v[o[rn]];j--){ f[tp][j]=max(f[tp][j],f[tp][j-v[o[rn]]]+w[o[rn]]); } rn--; } for(int j=0;j<=m;j++){ as1[nq[i].id]^=f[tp][j]*(unsigned long long)(j+1); as3[nq[i].id]^=f[tp][j]*(unsigned long long)(j+1)*(unsigned long long)(j+1)*(unsigned long long)(j+1); } } if(lr!=2)for(int i=1;i<=m;i++){ dp[0][tp][i]=dp[1][tp][i]=dp[lr][tp-1][i]; } for(int i=l;i<=mid;i++){ for(int j=m;j>=v[o[i]];j--){ dp[1][tp][j]=max(dp[1][tp][j],dp[1][tp][j-v[o[i]]]+w[o[i]]); } } for(int i=mid+1;i<=r;i++){ for(int j=m;j>=v[o[i]];j--){ dp[0][tp][j]=max(dp[0][tp][j],dp[0][tp][j-v[o[i]]]+w[o[i]]); } } for(int i=ql;i<=ql+cl-1;i++)q[i]=tl[i-ql+1]; for(int i=ql+cl;i<=qr-cr;i++)q[i]=nq[i-ql-cl+1]; for(int i=qr-cr+1;i<=qr;i++)q[i]=tr[i-qr+cr]; if(l!=r)fz(l,mid,ql,ql+cl-1,tp+1,0); if(l!=r)fz(mid+1,r,qr-cr+1,qr,tp+1,1); } signed main(){init(); scanf("%lld%lld%lld",&n,&m,&T); for(int i=1;i<=n;i++){ scanf("%lld",&v[i]); } for(int i=1;i<=n;i++){ scanf("%lld",&w[i]); } for(int i=2;i<=n;i++){ int fa; scanf("%lld",&fa); add_side(fa,i); } dfn(1); for(int i=2;i<=n;i++){ q[i-1].l=d[i];q[i-1].r=s[i];q[i-1].id=i; } sort(q+1,q+n,cmp); fz(1,n,1,n-1,0,2); for(int i=2;i<=n;i++){ printf("%llu %llu\n",as1[i],as3[i]); } return 0; }