[LCT]SCOI2018：tree

Description：

在大小為 N 的樹上，點從 1 到 N 标号，第 i 個點有權值 Ai，現在需要支援兩 種操作：

第一種操作格式為“1 U” ，表示詢問從 U 出發的簡單路徑，經過的點權值 之和的最大值；

第二種操作格式為“2 U V” ，表示将 U 的權值修改為 V。

Data Range：

對于 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

Solution：

類似Qtree，每個點維護一個multiset表示其虛子樹的路徑權值和最大值

然後實鍊維護上下在目前鍊上的路徑權值和以及鍊的所有虛子樹權值和，就好修改了

詢問就把一個點變成鍊底，直接查詢就完了

Code：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
    while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
    return res*f;
}
const int INF=1e9,N=1e5+5;
int vis[N<<1],head[N<<1],nxt[N<<1],fr[N<<1],tot=0;
inline void add(int x,int y){vis[++tot]=y;nxt[tot]=head[x];head[x]=tot;fr[tot]=x;}
multiset<int,greater<int> >s[N];
multiset<int,greater<int> >::iterator it;
int get(int x){
    if(!s[x].size()) return -INF;
    else return (*s[x].begin());
}
namespace LCT{ 
    int ls[N],rs[N],fa[N],siz[N],val[N],lmx[N],rmx[N];
    inline void pushup(int x){
        siz[x]=val[x];
        if(ls[x]) siz[x]+=siz[ls[x]];
        if(rs[x]) siz[x]+=siz[rs[x]];
        lmx[x]=max(lmx[ls[x]],siz[ls[x]]+max(val[x],max(get(x),lmx[rs[x]])+val[x]));
        rmx[x]=max(rmx[rs[x]],siz[rs[x]]+max(val[x],max(get(x),rmx[ls[x]])+val[x]));
    }
    inline int isrs(int x){return rs[fa[x]]==x;}
    inline bool isroot(int x){
        if(!fa[x]) return 1;
        return ls[fa[x]]!=x && rs[fa[x]]!=x;
    }
    inline void rotate(int x){
        int y=fa[x],z=fa[y],b=ls[y]==x?rs[x]:ls[x];
        if(z && !isroot(y)) (ls[z]==y?ls[z]:rs[z])=x;
        fa[x]=z,fa[y]=x;b?fa[b]=y:0;
        if(ls[y]==x) rs[x]=y,ls[y]=b;
        else ls[x]=y,rs[y]=b;
        pushup(y);pushup(x);
    }
    inline void splay(int x){
        while(!isroot(x)){
            if(!isroot(fa[x])){
                if(isrs(x)==isrs(fa[x])) rotate(fa[x]);
                else rotate(x);
            }
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x){
        for(int y=0;x;y=x,x=fa[x]){
            splay(x);
            if(rs[x]) s[x].insert(lmx[rs[x]]);
            if(y){
                it=s[x].find(lmx[y]);
                s[x].erase(it);
            }
         rs[x]=y;pushup(x);
        }
    }
}
using namespace LCT;
void dfs(int v,int f){
    siz[v]=ls[v]=rs[v]=val[v]=lmx[v]=rmx[v]=0;
    fa[v]=f;s[f].insert(0);
    for(int i=head[v];i;i=nxt[i]) dfs(vis[i],v);
}
int main(){
    lmx[0]=rmx[0]=-INF;
    int n=read(),q=read();
    for(int x,i=2;i<=n;i++){x=read();add(x,i);}
    dfs(1,0);
    for(int i=1;i<=n;i++){access(i);splay(i);val[i]=read();pushup(i);}
    while(q--){
        int op=read();
        if(op==1){
            int x=read();
            access(x);splay(x);cout<<rmx[x]<<"\n";
        }
        else{
            int x=read(),y=read();
            access(x);splay(x);val[x]=y;pushup(x);
        }
    }
    return 0;
}