AOJ 2450 Do use segment tree

重い。ただただ重い。

#define MAX_N 200100
#define MAX_LOG_V 20
 
const int SIZE = 1<<19;
struct node{
	int l,m,r,sum,lazy,ig;
	node(){
		l = m = r = sum = ig = 0;
		lazy = INF;
	}
	node(int _ig){
		l = m = r = sum = 0;
		lazy = INF;
		ig = _ig;
	}
};
node update_node(node lch,node rch){
	if(lch.ig)return rch;
	if(rch.ig)return lch;
	node ret;
	ret.m = max(max(lch.m,rch.m),lch.r+rch.l);
	ret.l = max(lch.l,lch.sum+rch.l);
	ret.r = max(rch.r,lch.r+rch.sum);
	ret.sum = lch.sum+rch.sum;
	return ret;
}
struct segtree{
    node seg[SIZE*2];
    void lazy_evaluate(int k,int l,int r){
    	if(seg[k].lazy==INF)return;
        seg[k].m = max(seg[k].lazy*(r-l),seg[k].lazy);
        seg[k].l = seg[k].m;
        seg[k].r = seg[k].m;
        seg[k].sum = seg[k].lazy*(r-l);
        if(k<SIZE-1){
            seg[k*2+1].lazy = seg[k].lazy;
            seg[k*2+2].lazy = seg[k].lazy;
        }
        seg[k].lazy=INF;
    }
    void update(int a,int b,int k,int l,int r,int x){
        lazy_evaluate(k,l,r);
        if(r<=a||b<=l)return;
        else if(a<=l&&r<=b){
            seg[k].lazy = x;
            lazy_evaluate(k,l,r);
            return;
        }else{
            update(a,b,k*2+1,l,(l+r)/2,x);
            update(a,b,k*2+2,(l+r)/2,r,x);
            seg[k] = update_node(seg[k*2+1],seg[k*2+2]);
        }
    }
    void update(int a,int b,ll x){
    	if(a>=b)return;
        update(a,b,0,0,SIZE,x);
    }
    node query(int a,int b,int k,int l,int r){
        lazy_evaluate(k,l,r);
        if(r<=a||b<=l)return node(1);
        else if(a<=l&&r<=b)return seg[k];
        else{
            node lch = query(a,b,k*2+1,l,(l+r)/2);
            node rch = query(a,b,k*2+2,(l+r)/2,r);
            seg[k] = update_node(seg[k*2+1],seg[k*2+2]);
            return update_node(lch,rch);
        }
    }
   	node query(int a,int b){
   		if(a>=b)return node(1);
        return query(a,b,0,0,SIZE);
    }
}seg;
struct HeavyLightDecomposition{
    vector<int> g[MAX_N];
    int N,root;
    int par[MAX_N];
    int depth[MAX_N],chnum[MAX_N];
    void add_edge(int a,int b){
        g[a].pb(b);
        g[b].pb(a);
    }
    struct state{
        int v,p,d;
        bool go;
        state(int v,int p,int d,bool go):v(v),p(p),d(d),go(go){}
        state(int v,int p,bool go):v(v),p(p),go(go){}
    };
    void init(){
        dfs();
        decompose();
        construct_toseg();
    }
    void dfs(){
        stack<state> st;
        st.push(state(0,-1,0,true));
        while(!st.empty()){
            state now = st.top();
            st.pop();
            int v = now.v,p = now.p,d = now.d;
            if(now.go){
                depth[v]=d;
                par[v]=p;
                st.push(state(v,p,d,false));
                for(int i=0;i<g[v].size();i++){
                    if(g[v][i]==p)continue;
                    st.push(state(g[v][i],v,d+1,true));
                }
            }else{
                chnum[v]=1;
                for(int i=0;i<g[v].size();i++){
                    chnum[v]+=chnum[g[v][i]];
                }
            }
        }
        return;
    }
    vector<int> top;
    int head[MAX_N];
    int heavy[MAX_N];
    int toseg[MAX_N];
    int chain_len[MAX_N];
    void decompose(){
        stack<state> st;
        st.push(state(0,-1,true));
        while(!st.empty()){
            state now = st.top();
            st.pop();
            int v=now.v,p=now.p,istop=now.go;
            if(istop)top.pb(v);
            int hev = -1;
            int val = -1;
            for(int i=0;i<g[v].size();i++){
                if(g[v][i]==p)continue;
                if(val<chnum[g[v][i]]){
                    val = chnum[g[v][i]];
                    hev = g[v][i];
                }
            }
            heavy[v]=hev;
            for(int i=0;i<g[v].size();i++){
                if(g[v][i]==p)continue;
                if(g[v][i]==hev)st.push(state(g[v][i],v,false));
                else st.push(state(g[v][i],v,true));
            }
        }
    }
    void construct_toseg(){
        int id = 0;
        for(int i=0;i<top.size();i++){
            int now = top[i];
            while(1){
                if(now==-1)break;
                toseg[now]=id++;
                head[now]=top[i];
                now = heavy[now];
                chain_len[top[i]]++;
            }
        }
    }
    int lca(int u,int v){
        while(head[u]!=head[v]){
            if(depth[head[u]]<depth[head[v]])swap(u,v);
            u = par[head[u]];
        }
        return (depth[u]<depth[v])?u:v;
    }
    void update(int u,int v,int x){
    	if(u==v){
    		seg.update(toseg[u],toseg[u]+1,x);
    		return;
    	}
    	int lc = lca(u,v);
    	int nu = u,nv = v;
    	while(depth[head[nu]]>depth[lc]){
            seg.update(toseg[head[nu]],toseg[nu]+1,x);
            nu = par[head[nu]];
        }
        seg.update(toseg[lc],toseg[nu]+1,x);
    	while(depth[head[nv]]>depth[lc]){
            seg.update(toseg[head[nv]],toseg[nv]+1,x);
            nv = par[head[nv]];
        }
        seg.update(toseg[lc],toseg[nv]+1,x);
    }
    int query(int u,int v){
    	if(u==v)return seg.query(toseg[u],toseg[u]+1).m;
    	int lc = lca(u,v);
    	int nu=u,nv=v;
    	node ansu = node(1);
    	node ansv = node(1);
    	while(depth[head[nu]]>depth[lc]){
            ansu = update_node(seg.query(toseg[head[nu]],toseg[nu]+1),ansu);
            nu = par[head[nu]];
        }
        bool flag = false;
        if(nu!=lc){
        	ansu = update_node(seg.query(toseg[lc],toseg[nu]+1),ansu);
        	flag = true;
        }
    	while(depth[head[nv]]>depth[lc]){
            ansv = update_node(seg.query(toseg[head[nv]],toseg[nv]+1),ansv);
            nv = par[head[nv]];
        }
        if(!flag){
        	ansv = update_node(seg.query(toseg[lc],toseg[nv]+1),ansv);
        }
        swap(ansu.l,ansu.r);
        node ans = update_node(ansu,ansv);
        return ans.m;       
    }
}hld;
 
int N,Q;
int w[200100];
int main(){
    scanf("%d %d",&N,&Q);
    hld.N = N;
    for(int i=0;i<N;i++)scanf("%d",&w[i]);
    for(int i=0;i<N-1;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        a--;b--;
        hld.add_edge(a,b);
    }
    hld.root = 0;
    hld.init();
    for(int i=0;i<N;i++)hld.update(i,i,w[i]);
    for(int i=0;i<Q;i++){
        int t,u,v,x;
        scanf("%d %d %d %d",&t,&u,&v,&x);
        u--;v--;
        if(t==1)hld.update(u,v,x);
        else printf("%d\n",hld.query(u,v));
    }
    return 0;
}