#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; //#include "atcoder/all" // using namespace atcoder; //#pragma GCC optimize(3) //#pragma GCC optimize("Ofast") #define endl "\n" #define int unsigned long long #define double long double #define pii pair<int, int> #define p1(x) (x).first #define p2(x) (x).second #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) #define i128 __int128_t int n,M,T; int f[20][20030]; int w[100300],c[100300]; inline void chkmx(int &x,int y){ x=max(x,y); } int res1,res3; inline int pw(int x,int y){ if(y==1)return x; else return x*x*x; } int ANS1[100300],ANS3[100300]; inline void upd(int *f){ res1=0,res3=0; for(int i=0;i<=M;i++) res1^=f[i]*pw(i+1,1), res3^=f[i]*pw(i+1,3); } vector<int>g[100030]; int dfn[100030],siz[100030]; int p[100300],tk; inline void dfs(int u){ p[dfn[u]=++tk]=u; siz[u]=1; for(int v:g[u]) dfs(v),siz[u]+=siz[v]; } inline void ins(int x,int y,int id){ memcpy(f[y],f[x],sizeof(f[x])); for(long long i=M-c[id];i>=0;i--) chkmx(f[y][i+c[id]],f[x][i]+w[id]); } inline void calc(int l,int r,vector<pii>T,int d){ if(T.empty())return ; if(l>r)return ; int mid=l+r>>1; vector<pii>L,R,S; for(pii e:T) if(p1(e)<mid)L.push_back(e); else if(p2(e)>mid)R.push_back(e); else S.push_back(e); ins(d,d+1,0); for(int i=mid;i<=r;i++) ins(d+1,d+1,p[i]); calc(l,mid-1,L,d+1); ins(d,d+1,0); for(int i=l;i<=mid;i++) ins(d+1,d+1,p[i]); calc(mid+1,r,R,d+1); for(pii e:S){ while(l<p1(e)) ins(d,d,l++); while(r>p2(e)) ins(d,d,r--); upd(f[d]); ANS1[p[p1(e)]]=res1; ANS3[p[p1(e)]]=res3; } } inline void slv(){ cin>>n>>M>>T; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=2;i<=n;i++){ int v; cin>>v; g[v].push_back(i); } dfs(1); vector<pii>E; for(int i=2;i<=n;i++) E.push_back({dfn[i],dfn[i]+siz[i]-1}); sort(E.begin(),E.end()); calc(1,n,E,1); for(int i=2;i<=n;i++) cout<<ANS1[i]<<" "<<ANS3[i]<<endl; } inline void MT(){ int t; cin>>t; while(t--)slv(); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // MT(); slv(); cout.flush(); return 0; } /* */