【Codeforces 1178G】The Awesomest Vertex
分块+凸包
题目大意：
给定一棵有根树，每个点有权值 $a_i$ 和 $b_i$。
对于一个结点 $v$，记 $R(v)$ 表示 $v$ 的祖先集合，则 $v$ 的贡献为：
需要支持两个操作：
- 给定 $v,x$，把 $a_v$ 的值加上 $x$。$x$为正整数。
- 给定 $v$，问以 $v$ 为根的子树中，贡献最大的结点的贡献。
题解：
分块+凸包的套路题。虽然一眼秒了不过就是想写一遍啊
考虑记 $B_v=\left|\sum\limits_{w\in R(v)}b_w \right|$，这个值显然不会变。
再考虑令 $A_v=\sum\limits_{w\in R(v)}a_w$，然后我们直接维护 $A_v$ 的值。
考虑单点修改操作，会对 $v$ 所在的所有子树中的 $A$ 的值进行变化。
那么相当于一个子树修改子树查询问题，用 dfs 序转化为序列问题。
考虑将 $(B_v,A_v\times B_v)$ 当做二维平面上的一个点，并对所有 $A$ 整体加上$\Delta A$，考虑哪些点可能成为最大值。
不难发现，只有在上凸壳上面的点，才可能在 $A_v$ 加上某个值后成为答案。容易用叉积、斜率等方式证明。
考虑分块，对每个块维护凸包。那么对于全局修改，可以直接在块上打标记。询问整个块的答案的时候，直接在凸包上二分最大值即可。对于边角修改，暴力即可，修改完重构凸包。
观察到 $x$ 为正，那么 $\Delta A$ 始终变大，最大值在凸包上的位置单调向右移动。所以直接使用一个指针指向当前最大值，然后往右移动即可。边角修改的时候，把指针复原到最左边即可。复杂度均摊正确。
由于产生贡献的是 $|A_v|$，所以我们对 $A_v$ 和 $-A_v$ 分别维护凸包即可。维护负数的时候，由于 $\Delta A$ 单调变小，所以指针要从右往左移。
时间复杂度 $O(m\sqrt n)$。
Code：
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
#define bel(x)((x-1)/siz+1)
const int N=2e5+5,siz=512,BL=N/siz+2;
typedef long long LL;
int n,q,fa[N],head[N],cnt,a[N],b[N],dfn[N],idx,sz[N],L[BL],R[BL],idfn[N];
int blocks;
int A[N],B[N];
struct edge{
int to,nxt;
}e[N];
struct hull{
struct point{
int x;
LL y;
inline point operator-(const point&rhs)const{return(point){x-rhs.x,y-rhs.y};}
};
inline int cross(point a,point b){
if(a.x*b.y==a.y*b.x)return 0;
if(a.x*b.y>a.y*b.x)return 1;
return -1;
}
vector<point>pt;
int it;
inline void clear(){pt.clear();}
inline void insert(int x,LL y){
point s=(point){x,y};
while(pt.size()>1){
if(cross(s-pt[pt.size()-2],pt[pt.size()-1]-pt[pt.size()-2])==1)break;else pt.pop_back();
}
pt.push_back(s);
}
inline LL getans(LL dlt,const int fh){
while(it+fh>=0&&it+fh<pt.size()&&pt[it].x*dlt+pt[it].y<pt[it+fh].x*dlt+pt[it+fh].y)
it+=fh;
return pt[it].x*dlt+pt[it].y;
}
};
struct BLOCK{
pair<int,int>b[siz];
int l,r,len;
hull h1,h2;
LL dlt;
inline void build(){
for(int i=1;i<=len;++i){
h1.insert(b[i].first,b[i].first*(LL)A[b[i].second]);
h2.insert(b[i].first,-b[i].first*(LL)A[b[i].second]);
}
h1.it=0,h2.it=h2.pt.size()-1;
}
inline void init(int L,int R){
l=L,r=R,len=r-l+1;
for(int i=1;i<=len;++i)
b[i]=make_pair(B[L+i-1],L+i-1);
sort(b+1,b+len+1);
build();
}
void modify(int L,int R,int v){
for(int i=L;i<=R;++i)
A[i]+=v;
h1.clear(),h2.clear();
build();
}
inline LL ask(int L,int R){
LL ret=0;
for(int i=L;i<=R;++i)
ret=max(ret,llabs((LL)(A[i]+dlt)*B[i]));
return ret;
}
inline LL get(){
return max(h1.getans(dlt,1),h2.getans(-dlt,-1));
}
}G[BL];
void dfs(int now){
idfn[dfn[now]=++idx]=now,sz[now]=1;
a[now]+=a[fa[now]],b[now]+=b[fa[now]];
for(int i=head[now];i;i=e[i].nxt)dfs(e[i].to),sz[now]+=sz[e[i].to];
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=2;i<=n;++i){
cin>>fa[i];
e[++cnt]=(edge){i,head[fa[i]]},head[fa[i]]=cnt;
}
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)cin>>b[i];
dfs(1);
blocks=bel(n);
for(int i=1;i<=blocks;++i)L[i]=R[i-1]+1,R[i]=i*siz;
R[blocks]=n;
for(int i=1;i<=n;++i)
A[i]=a[idfn[i]],B[i]=abs(b[idfn[i]]);
for(int i=1;i<=blocks;++i)G[i].init(L[i],R[i]);
while(q--){
int op;
cin>>op;
if(op==1){
int v,x;
cin>>v>>x;
int l=dfn[v],r=dfn[v]+sz[v]-1;
const int bL=bel(l),bR=bel(r);
if(bL==bR)G[bL].modify(l,r,x);else{
G[bL].modify(l,R[bL],x);
G[bR].modify(L[bR],r,x);
for(int i=bL+1;i<bR;++i)
G[i].dlt+=x;
}
}else{
int v;
cin>>v;
int l=dfn[v],r=dfn[v]+sz[v]-1;
const int bL=bel(l),bR=bel(r);
LL ans=0;
if(bL==bR)
ans=G[bL].ask(l,r);
else{
ans=max(ans,max(G[bL].ask(l,R[bL]),G[bR].ask(L[bR],r)));
for(int i=bL+1;i<bR;++i)
ans=max(ans,G[i].get());
}
cout<<ans<<'\n';
}
}
return 0;
}