首先通过dfs序把子树操作转化为区间操作，求最大值可以用斜率优化。
然后分个块，对每个块维护个凸包。修改时中间的打个标记，边角暴力重构；询问时中间的用斜率优化的方法求，边角的暴力求。
由于此题有绝对值，所以还要对原值取负后再维护一个凸包。。。。
时间复杂度(O(nlogn+q sqrt n))
代码很丑，感觉不是人看的。。
官方题解讲得比我好多了。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cassert>
#include<cmath>
#define LL long long
#define ldb long double
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frz(i,x,y) for(int i=(x),z=y;i<=z;i++)
using namespace std;
const int N=200006;
const int M=N<<1;
const int BM=505;
int n,q,m;
int cnt,head[N],Next[M],v[M];
int a[N],b[N],c[N],d[N];
int clo,pre[N],dfn[N],ver[N];
struct data{
int x,y;
};
int bm;
void chkmax(LL &x,LL y){ if (y>x) x=y; }
int cmp1(const int &q,const int &w){ return d[q]<d[w]; }
int cmp2(const int &q,const int &w){ return -d[q]<-d[w]; }
struct blo{
int num[BM],l,r;
int inc;
LL x[BM],y[BM];
int h[BM],t,w;
LL chk(LL x1,LL y1,LL x2,LL y2){
return x1*y2-x2*y1;
}
void AddPoint(int i){
for(;w-1>=t&&chk(x[h[w]]-x[h[w-1]],y[h[w]]-y[h[w-1]],x[i]-x[h[w]],y[i]-y[h[w]])>=0;w--);
h[++w]=i;
}
LL query(){
for(;w-1>=t&&x[h[t]]*inc+y[h[t]]<=x[h[t+1]]*inc+y[h[t+1]];t++);
return x[h[t]]*inc+y[h[t]];
}
void build(){
//int bl,r=br;
t=1;w=0;
assert(r<=n);assert(r-l<=m);
fr(i,0,r-l) x[i]=d[num[i]],y[i]=1LL*c[num[i]]*d[num[i]],AddPoint(i);
}
void init(){
assert(r<=n);assert(r-l<=m);assert(m<BM);
fr(i,l,r) num[i-l]=i;
sort(num,num+r-l+1,cmp1);
build();
}
}bo[BM];
struct bloo{
int num[BM],l,r;
int inc;
LL x[BM],y[BM];
int h[BM],t,w;
LL chk(LL x1,LL y1,LL x2,LL y2){
return x1*y2-x2*y1;
}
void AddPoint(int i){
for(;w-1>=t&&chk(x[h[w]]-x[h[w-1]],y[h[w]]-y[h[w-1]],x[i]-x[h[w]],y[i]-y[h[w]])>=0;w--);
h[++w]=i;
}
LL query(){
for(;w-1>=t&&x[h[t]]*inc+y[h[t]]<=x[h[t+1]]*inc+y[h[t+1]];t++);
return x[h[t]]*inc+y[h[t]];
}
void build(){
//int bl,r=br;
t=1;w=0;
assert(r<=n);assert(r-l<=m);
fr(i,0,r-l) x[i]=-d[num[i]],y[i]=-1LL*c[num[i]]*d[num[i]],AddPoint(i);
}
void init(){
assert(r<=n);assert(r-l<=m);assert(m<BM);
fr(i,l,r) num[i-l]=i;
sort(num,num+r-l+1,cmp2);
build();
}
}boo[BM];
void read(int &x){
char ch=getchar();x=0;int w=0;
for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
if (w) x=-x;
}
void add(int x,int y){
Next[++cnt]=head[x];
head[x]=cnt;
v[cnt]=y;
}
void dfs(int x,int fa){
pre[x]=++clo;ver[clo]=x;
a[x]+=a[fa];b[x]+=b[fa];
for(int i=head[x];i;i=Next[i])
if (v[i]!=fa) dfs(v[i],x);
dfn[x]=clo;
}
void init(){
m=sqrt(n);
fr(i,1,n) c[i]=a[ver[i]],d[i]=b[ver[i]];
bo[0].l=1;bo[0].r=m-1;bm=n/m; //not real
for(int i=m;i<=n;i+=m) bo[i/m].l=i,bo[i/m].r=i+m-1;
bo[bm].r=n;
fr(o,0,bm){
//int &l=bo[o].r,&r=bo[o].r;
boo[o].l=bo[o].l;boo[o].r=bo[o].r;
bo[o].init();boo[o].init();
}
}
void incc(int l,int r,int v){
if (l/m==r/m){
fr(i,l,r) c[i]+=v;
bo[l/m].build();boo[l/m].build();
return;
}
frz(i,l,bo[l/m].r) c[i]+=v;bo[l/m].build();boo[l/m].build();
fr(i,bo[r/m].l,r) c[i]+=v;bo[r/m].build();boo[r/m].build();
frz(i,l/m+1,r/m-1) bo[i].inc+=v,boo[i].inc+=v;
}
LL query(int l,int r){
LL ans=-1000000000000000000;
if (l/m==r/m){
fr(i,l,r) chkmax(ans,1LL*abs(c[i]+bo[l/m].inc)*d[i]);
return ans;
}
frz(i,l,bo[l/m].r) chkmax(ans,1LL*abs(c[i]+bo[l/m].inc)*d[i]);
fr(i,bo[r/m].l,r) chkmax(ans,1LL*abs(c[i]+bo[r/m].inc)*d[i]);
frz(i,l/m+1,r/m-1) chkmax(ans,bo[i].query()),chkmax(ans,boo[i].query());
return ans;
}
int main(){
read(n);read(q);
int tp,x,y;
fr(i,2,n){
read(x);
add(x,i);add(i,x);
}
fr(i,1,n) read(a[i]);
fr(i,1,n) read(b[i]);
dfs(1,0);
fr(i,1,n) b[i]=abs(b[i]);
init();
while(q--){
read(tp);read(x);
if (tp==1){
read(y);
incc(pre[x],dfn[x],y);
} else{
printf("%lld
",query(pre[x],dfn[x]));
}
}
return 0;
}