// // main.cpp // 抗体(antibody) // // Created by Y2y7m on 2023/12/7. // Copyright © 2023年 Slip. All rights reserved. // #include <iostream> #include <vector> using namespace std; #define int long long #define ull unsigned long long const int maxn=1e5+10,maxm=2e4+10; int n,m,T; int w[maxn],v[maxn]; vector<int> edge[maxn]; int dfn[maxn],tot,sz[maxn]; void dfs(int u) { dfn[u]=++tot,sz[u]=1; for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; dfs(v); sz[u]+=sz[v]; } } struct node { int l,r; int id; }; bool cmp(node x,node y) { return x.l<y.l; } int f[maxm]; ull ans1[maxn],ans2[maxn]; void sol(int l,int r,vector<node> query) { if(l>r) return ; if(query.empty()) return ; if(l==r) { node tmp=query[0]; ull t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*1ull*(i+1); ans1[tmp.id]=t; t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*1ull*(i+1)*1ull*(i+1)*1ull*(i+1); ans2[tmp.id]=t; return ; } int mid=(l+r)>>1; vector<int> save; for(int i=0;i<=m;i++) save.push_back(f[i]); vector<node> t; for(node x:query) if(x.r<=mid) t.push_back(x); for(int i=mid+1;i<=r;i++) for(int j=m;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+v[i]); sol(l,mid,t); for(int i=0;i<=m;i++) f[i]=save[i]; for(int i=l;i<=mid;i++) for(int j=m;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+v[i]); t.clear(); for(node x:query) if(x.l>mid) t.push_back(x); sol(mid+1,r,t); t.clear(); for(int i=0;i<=m;i++) f[i]=save[i]; for(node x:query) if(x.l<=mid&&x.r>mid) t.push_back(x); int lpos=l,rpos=r; for(node x:t) { while(lpos<x.l) { for(int j=m;j>=w[lpos];j--) f[j]=max(f[j],f[j-w[lpos]]+v[lpos]); lpos++; } while(rpos>x.r) { for(int j=m;j>=w[rpos];j--) f[j]=max(f[j],f[j-w[rpos]]+v[rpos]); rpos--; } ull t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*(i+1); ans1[x.id]=t; t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*1ull*(i+1)*1ull*(i+1)*1ull*(i+1); ans2[x.id]=t; } for(int i=0;i<=m;i++) f[i]=save[i]; } signed main() { ios::sync_with_stdio(false); cin>>n>>m>>T; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++) cin>>v[i]; int x; for(int i=2;i<=n;i++) { cin>>x; edge[x].push_back(i); } dfs(1); vector<node> ask; for(int i=1;i<=n;i++) ask.push_back({dfn[i],dfn[i]+sz[i]-1,i}); sort(ask.begin(),ask.end(),cmp); sol(1,n,ask); for(int i=2;i<=n;i++) cout<<ans1[i]<<" "<<ans2[i]<<endl; return 0; } /* 3 3 0 1 1 1 1 1 1 1 2 */