树
时间限制 3000ms
内存限制 64MB
【题目描述】
在大小为 N 的树上，点从 1 到 N 标号，第 i 个点有权值 Ai，现在需要支持两种操作：
第一种操作格式为“1 U”，表示询问从 U 出发的简单路径，经过的点权值之和的最大值；
第二种操作格式为“2 U V”，表示将 U 的权值修改为 V。
【输入格式】
第一行两个整数 N 和 M，表示树的大小和操作数；
第二行 N-1 个整数，第 i 个整数 Pi(1<=Pi<=i)表示第 i+1 个点与 Pi 有边相连；
第三行 N 个整数，第 i 个整数 Ai 表示第 i 个点的点权；
接下来 M 行，每行为一个询问操作“1 U”或修改操作“2 U V”，按操作发生的先后顺序给出。
【输出格式】
对于每个询问操作，输出一个整数，即经过的点权值之和的最大值。
【样例输入 1】
6 7
1 1 1 3 3
-1 2 -3 4 -5 6
1 2
1 5
1 6
2 4 5
1 2
1 5
1 6
【样例输出 1】
5
-2
6
6
-2
7
【数据范围】
对于 10%的数据，满足：
1<=N<=1000,1<=M<=1000
对于另外 20%的数据，不存在修改操作
对于另外 20%的数据，满足 Pi=i
对于 100%的数据，满足：
1<=N<=100000，1<=M<=100000
1<=Pi<=i，-10000<=Ai<=10000
1<=U<=n，-10000<=V<=10000
分析
如果没有修改，那么就是一个简单的换根DP，选儿子中的最大值或者0即可。有修改的话，就要用到动态DP，如果用LCT维护的话换根就很方便了，维护正反矩阵乘积即可。矩阵转移为：
\[\begin{bmatrix}
v[i] & v[i]+g[i].max & v[i] \\
-\infty & 0 & -\infty \\
-\infty & -\infty & 0
\end{bmatrix}*
\begin{bmatrix}
f(i+1)\\
0\\
0
\end{bmatrix}
\]
比较麻烦的是轻儿子的向上更新，由于要选最大值，所以要对每个节点维护一个平衡树（multiset），支持快速插入删除以及查询最大值。这个操作的复杂度应该跟splay一起均摊。
时间复杂度\(O(n \log n + 27 m \log n)\)。
代码
不开O2=TLE，开了O2跑得过动态点分治。很有必要学习动态点分治了。
co int N=1e5+1;
co ll INF=1e18;
struct matrix{
ll a[3][3];
il ll*operator[](int i) {return a[i];}
il co ll*operator[](int i)co {return a[i];}
il void init(ll v,co multiset<ll>&g){
a[0][0]=v,a[0][1]=v+(g.size()?*g.rbegin():0),a[0][2]=v;
a[1][0]=-INF,a[1][1]=0,a[1][2]=-INF;
a[2][0]=-INF,a[2][1]=-INF,a[2][2]=0;
}
il ll get() {return max(a[0][0],max(a[0][1],a[0][2]));}
il matrix operator*(co matrix&b)co{
matrix c;for(rg int i=0;i<3;++i) fill(c[i],c[i]+3,-INF);
for(rg int i=0;i<3;++i)
for(rg int j=0;j<3;++j)
for(rg int k=0;k<3;++k) c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
return c;
}
}p1[N],p2[N];
int fa[N],ch[N][2];
ll v[N];
multiset<ll> g[N];
#define lc ch[x][0]
#define rc ch[x][1]
il bool nroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
il void pushup(int x){
p1[x].init(v[x],g[x]),p2[x].init(v[x],g[x]);
if(lc) p1[x]=p1[lc]*p1[x],p2[x]=p2[x]*p2[lc];
if(rc) p1[x]=p1[x]*p1[rc],p2[x]=p2[rc]*p2[x];
}
il void rotate(int x){
int y=fa[x],z=fa[y],l=ch[y][1]==x,r=l^1;
if(nroot(y)) ch[z][y==ch[z][1]]=x;fa[x]=z;
ch[y][l]=ch[x][r],fa[ch[x][r]]=y;
ch[x][r]=y,fa[y]=x;
pushup(y);
}
il void splay(int x){
for(int y,z;nroot(x);rotate(x)){
y=fa[x],z=fa[y];
if(nroot(y)) rotate(y==ch[z][1]^x==ch[y][1]?x:y);
}
pushup(x);
}
il void access(int x){
for(int y=0;x;x=fa[y=x]){
splay(x);
if(rc) g[x].insert(p1[rc].get());
if(y) g[x].erase(g[x].find(p1[y].get()));
rc=y,pushup(x);
}
}
int main(){
freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
int n=read<int>(),m=read<int>();
for(rg int i=2;i<=n;++i) read(fa[i]);
for(rg int i=1;i<=n;++i) read(v[i]);
for(rg int i=n;i>=1;--i) p1[i].init(v[i],g[i]),p2[i].init(v[i],g[i]),g[fa[i]].insert(p1[i].get());
for(int u,v;m--;){
if(read<int>()==1){
read(u);
access(u),splay(u);
printf("%lld\n",p2[u].get());
}
else{
read(u),read(v);
access(u),splay(u),::v[u]=v,pushup(u);
}
}
return 0;
}
