Problem:


Do use segment tree

Given a tree with n (1 ≤ n ≤ 200,000) nodes and a list of q (1 ≤ q ≤ 100,000) queries,
process the queries in order and output a value for each output query.
The given tree is connected and each node on the tree has a weight wi (-10,000 ≤ wi ≤ 10,000).

Each query consists of a number ti (ti = 1, 2), which indicates the type of the query , and  three numbers ai, bi and ci (1 ≤ ai, bi ≤ n, -10,000 ≤ ci ≤ 10,000).
Depending on the query type, process one of the followings:

 (ti = 1: modification query)
Change the weights of all nodes on the shortest path between ai and bi (both inclusive) to ci.

 (ti = 2: output query) 
First, create a list of weights on the shortest path between ai and bi (both inclusive) in order. After that, output the maximum sum of a non-empty continuous subsequence of the weights on the list. ci is ignored for output queries.

Input

The first line contains two integers n and q.
 On the second line, there are n integers which indicate w1, w2, ... , wn.

Each of the following n - 1 lines consists of two integers si and ei (1 ≤ si, ei ≤ n),
which means that there is an edge between si and ei.

 Finally the following q lines give the list of queries, each of which contains four integers  in the format described above.
Queries  must be processed one by one from top to bottom.

Output

For each output query, output  the maximum sum in one line.

Sample Input 1

3 4
1 2 3
1 2
2 3
2 1 3 0
1 2 2 -4
2 1 3 0
2 2 2 0

Output for the Sample Input 1

6
3
-4

Sample Input 2

7 5
-8 5 5 5 5 5 5
1 2
2 3
1 4
4 5
1 6
6 7
2 3 7 0
2 5 2 0
2 4 3 0
1 1 1 -1
2 3 7 0

Output for the Sample Input 2

12
10
10
19

Sample Input 3

21 30
10 0 -10 -8 5 -5 -4 -3 1 -2 8 -1 -7 2 7 6 -9 -6 3 4 9
10 3
3 2
3 12
12 4
4 13
4 9
10 21
21 1
1 11
11 14
1 15
10 6
6 17
6 16
6 5
5 18
5 19
10 7
10 8
8 20
1 1 21 -10
1 3 19 10
2 1 13 0
1 4 18 8
1 5 17 -5
2 16 7 0
1 6 16 5
1 7 15 4
2 4 20 0
1 8 14 3
1 9 13 -1
2 9 18 0
1 10 12 2
1 11 11 -8
2 21 15 0
1 12 10 1
1 13 9 7
2 6 14 0
1 14 8 -2
1 15 7 -7
2 10 2 0
1 16 6 -6
1 17 5 9
2 12 17 0
1 18 4 6
1 19 3 -3
2 11 8 0
1 20 2 -4
1 21 1 -9
2 5 19 0

Output for the Sample Input 3

20
9
29
27
10
12
1
18
-2
-3



Sample input:
3 4
1 2 3
1 2
2 3
2 1 3 0
1 2 2 -4
2 1 3 0
2 2 2 0


Sample output:
6
3
-4

Submission status: Runtime Error

Solution code:
/*

  まだ途中セーヴ

  ci is ignored for output queries.
  このインプットは無視しろってこと？kamo
 */
#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;


typedef long long ll;

// -- segment tree with lazy propagation --- 

const int IINF = INT_MAX;
const char EMPTY = 'X';
 
struct Node{
  ll value,left,right,maxi;
  char lazy;
  ll lazy_coef; 
  Node(ll value=0,ll left=-INT_MAX,ll right=-INT_MAX,ll maxi=-INT_MAX,char lazy=EMPTY,ll lazy_coef=0):value(value),left(left),right(right),maxi(maxi),lazy(lazy),lazy_coef(lazy_coef){}
};
 
class SegmentTree{
public:
  vector<Node> RMQ;
  int limit,N; // N は要素数
 
  void init(int tmp){
    N = tmp;
    int N_N = 1;
    while(N_N < N)N_N *= 2;
    limit = N_N;
    RMQ.resize(3*limit);
    rep(i,3*limit-1) RMQ[i] = Node();
  }

  Node _build(int cur,int L,int R,const vector<int> &buf){

    if( !( 0 <= cur && cur < 2*limit-1 ) ) return Node();
    if( L == R-1 ){
      if( L >= N ) return Node();
      RMQ[cur].value = buf[L];
      RMQ[cur].left  = buf[L];
      RMQ[cur].right = buf[L];
      RMQ[cur].maxi  = buf[L];
    } else {
      Node vl = _build(cur*2+1,L,(L+R)/2,buf);
      Node vr = _build(cur*2+2,(L+R)/2,R,buf);
      RMQ[cur].value = vl.value + vr.value;
      RMQ[cur].left  = max(vl.left,vl.value+vr.left);
      RMQ[cur].right = max(vr.right,vr.value+vl.right);
      RMQ[cur].maxi  = max(vl.maxi,max(vr.maxi,vl.right+vr.left));
    }
    return RMQ[cur];
  }

  void build(const vector<int> &buf) { _build(0,0,limit,buf); }

  inline void value_evaluate(int index,int L,int R){
    if( RMQ[index].lazy == 'S' ){
      RMQ[index].value  = ( R - L ) * RMQ[index].lazy_coef;
      RMQ[index].left   = max(RMQ[index].lazy_coef,(R-L)*RMQ[index].lazy_coef);
      RMQ[index].right  = max(RMQ[index].lazy_coef,(R-L)*RMQ[index].lazy_coef);
      RMQ[index].maxi   = max(RMQ[index].lazy_coef,(R-L)*RMQ[index].lazy_coef);
    }
  }
   
  inline void lazy_evaluate(int index,int L,int R){
    value_evaluate(index,L,R);
    if( index < limit && RMQ[index].lazy != EMPTY ) {
      if( RMQ[index].lazy == 'S') {
        RMQ[index*2+1].lazy = RMQ[index*2+2].lazy = 'S';
        RMQ[index*2+1].lazy_coef = RMQ[index].lazy_coef;
        RMQ[index*2+2].lazy_coef = RMQ[index].lazy_coef;
      }
    }
    RMQ[index].lazy = EMPTY;
    RMQ[index].lazy_coef = 0;
  }

  inline void value_update(int index){
    RMQ[index].value = RMQ[index*2+1].value + RMQ[index*2+2].value;
    RMQ[index].left  = max(RMQ[index*2+1].left,RMQ[index*2+1].value+RMQ[index*2+2].left);
    RMQ[index].right = max(RMQ[index*2+2].right,RMQ[index*2+2].value+RMQ[index*2+1].right);
    RMQ[index].maxi  = max(RMQ[index*2+1].maxi,max(RMQ[index*2+2].maxi,RMQ[index*2+1].right+RMQ[index*2+2].left));
  }

  void _update(int a,int b,char opr,ll v,int index,int L,int R){
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a )return;
    if( a <= L && R <= b ){
      RMQ[index].lazy = opr; 
      if( opr == 'S' ) RMQ[index].lazy_coef = v; 
      lazy_evaluate(index,L,R); 
      return;
    }
 
    _update(a,b,opr,v,index*2+1,L,(L+R)/2);
    _update(a,b,opr,v,index*2+2,(L+R)/2,R);
    value_update(index);
 
  }

  void update(int a,int b,char opr,ll v){ _update(a,b,opr,v,0,0,limit); } 

  Node _query(int a,int b,int index,int L,int R){
    lazy_evaluate(index,L,R); 
 
    if( b <= L || R <= a ) return Node();
    if( a <= L && R <= b ) return RMQ[index];

    Node tmp1 = _query(a,b,index*2+1,L,(L+R)/2);
    Node tmp2 = _query(a,b,index*2+2,(L+R)/2,R);
    Node ret = Node();
    ret.value = tmp1.value + tmp2.value;
    ret.left  = max(tmp1.left,tmp1.value+tmp2.left);
    ret.right = max(tmp2.right,tmp2.value+tmp1.right);
    ret.maxi  = max(tmp1.maxi,max(tmp2.maxi,tmp1.right+tmp2.left));
    value_update(index); 
    return ret;
  }

  Node query(int a,int b) { return _query(a,b,0,0,limit); }

};

// -- segment tree with lazy propagation --- 

const int MAX_V = 201000;
struct Edge { int to,weight;};
int V;
vector<Edge> G[MAX_V];
vector<int> costs;

typedef pair<int,int> ii;

//RMQ LCA ------------------------------- begin
class LCA_RMQ{
private:
  int limit,N;
  vector<ii> dat;
public:
  void init(int n_){
    N = n_;
    dat.clear();
    limit = 1;
    while(limit<n_)limit*=2;
    dat.resize(2*limit);
    for(int i=0;i<2*limit-1;i++) dat[i] = ii(IINF,IINF);//ii(depth,index)
  }

  ii _build(int cur,int L,int R,const vector<ii> &buf){
    if( !( 0 <= cur && cur < 2*limit ) ) return ii(IINF,IINF);
    if( L == R-1 ) {
      if( L >= N ) return ii(IINF,IINF);
      dat[cur] = buf[L];
    } else {
      ii vl = _build(cur*2+1,L,(L+R)/2,buf);
      ii vr = _build(cur*2+2,(L+R)/2,R,buf);
      dat[cur] = min(vl,vr);
    }
    return dat[cur];
  }

  void build(const vector<ii> &buf){ _build(0,0,limit,buf); };
 
// k番めの値(0-indexed)をaに変更
  void update(int k,ii a){
    k += limit-1;
    dat[k] = a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = (dat[k*2+1].first>dat[k*2+2].first?dat[k*2+2]:dat[k*2+1]);
    }
  }
 
  ii _query(int a,int b,int k,int l,int r){
    if(r<=a || b<=l)return ii(IINF,-1);
    else if(a<=l && r<=b)return dat[k];
     
      ii vl = _query(a,b,k*2+1,l,(l+r)/2);
      ii vr = _query(a,b,k*2+2,(l+r)/2,r);

      return min(vl,vr);
  }

  ii query(int a,int b){ return _query(a,b,0,0,limit); }
};

int root;
vector<int> id,vs,depth;


void LCA_dfs(int v,int p,int d,int &k){
  id[v] = k;
  vs[k] = v;
  depth[k++] = d;
  for(int i=0;i<(int)G[v].size();i++){
    if(G[v][i].to != p){
      LCA_dfs(G[v][i].to,v,d+1,k);
      vs[k] = v;
      depth[k++] = d;
    }
  }
}

void LCA_init(int V,LCA_RMQ &rmq){
  root = 0;
  vs.clear();
  vs.resize(V*2,0);
  depth.clear();
  depth.resize(V*2,0);
  id.clear();
  id.resize(V);
  int k = 0;
  LCA_dfs(root,-1,0,k);
  rmq.init(k+1);  
  vector<ii> tmp;
  rep(i,k) tmp.push_back(ii(depth[i],vs[i]));
  rmq.build(tmp);
}

int lca(int u,int v,LCA_RMQ &rmq){ return rmq.query(min(id[u],id[v]),max(id[u],id[v])+1).second; }

//RMQ LCA ------------------------------- end

// Heavy Light Decomposition - begin

int chainNumber;
vector<int> subsize,chainID,headID,baseArray,posInBase,parent;



void HLD_dfs(int cur,int prev){
  parent[cur] = prev;
  rep(i,(int)G[cur].size()){
    int to = G[cur][i].to;
    if( to == prev ) continue;
    HLD_dfs(to,cur);
    subsize[cur] += subsize[to];
  }
}

void HLD(int cur,int prev,int &ptr){
  
  if( headID[chainNumber] == -1 ) headID[chainNumber] = cur;
  chainID[cur] = chainNumber;
  baseArray[ptr] = costs[cur];
  posInBase[cur] = ptr++;
  
  int maxi = -1;
  rep(i,(int)G[cur].size()) {
    int to = G[cur][i].to;
    if( to == prev ) continue;
    if( maxi == -1 || subsize[to] > subsize[maxi] ) maxi = to;
  }

  if( maxi != -1 ) HLD(maxi,cur,ptr);
  
  rep(i,(int)G[cur].size()){
    int to = G[cur][i].to;
    if( to == prev || to == maxi ) continue;
    ++chainNumber;
    HLD(to,cur,ptr);
  }

}

void HLD_init(){
  chainNumber = 0;

  subsize.clear();
  chainID.clear();
  headID.clear();
  baseArray.clear();
  posInBase.clear();
  parent.clear();

  subsize.resize(V,1);
  chainID.resize(V,-1);
  headID.resize(V,-1);
  baseArray.resize(V,-IINF);
  posInBase.resize(V,-1);
  parent.resize(V,-1);

  HLD_dfs(0,-1);
  int ptr = 0;
  HLD(0,-1,ptr);

}



// Heavy Light Decomposition - end

ll LLINF = LLONG_MAX;
bool DEBUG = false;

void print(Node a){
  puts("---");
  cout << "sum   = " << a.value << endl;
  cout << "left  = " << a.left << endl;
  cout << "right = " << a.right << endl;
  cout << "maxi  = " << a.maxi << endl;
}


ll special;
Node _Query(int s,int t,SegmentTree &seg,int f){
  if( !f && s == t ) {
    int ps = posInBase[s], pt = posInBase[t];
    if( ps > pt ) swap(ps,pt);
    Node node = seg.query(ps,pt+1);
    if( t == pt ) special = node.right;
    else          special = node.left;
    return node;
  }
  if( f && s == t ) {
    special = 0;
    return Node();
  }

  int chain_s,chain_t=chainID[t];
  Node ret = Node();
  while(1){
    chain_s = chainID[s];
    if( chain_s == chain_t ) {
      int ps = posInBase[s], pt = posInBase[t];
      int t_pos = pt;
      if( f && s == t ) {
        return ret;
      }
      if( ps > pt ) swap(ps,pt);
      if( f && t_pos == pt ) --pt;
      if( f && t_pos == ps ) ++ps;
      if( ps > pt ) swap(ps,pt);
      Node temp = seg.query(ps,pt+1);

      /*
      if( DEBUG ){
        cout << "$$$$$$$$$$$$$$$" << endl;
        print(temp);
        print(ret);
        cout << "XXXXXXXXXXXXXXX" << endl;
      }
      */
      /*
      if( t_pos == pt ) {
        swap(ret.left,ret.right);
      } else {
        swap(temp.left,temp.right);
      }
      */
      ret.maxi   = max(ret.maxi,max(temp.maxi,ret.right+temp.left));
      ret.left   = max(ret.left,ret.value+temp.left);
      ret.right  = max(temp.right,temp.value+ret.right);
      ret.value += temp.value;

      if( t_pos == pt ) {
        special = ret.left;
      } else {
        special = ret.right;
      }

      /*
      if( DEBUG ) {
        cout << "!!!!!!!!!!" << endl;
        print(ret);
        cout << "??????????" << endl;
      }
      */
      return ret;
    } else {
      int head = headID[chain_s];
      int ps = posInBase[s], ph = posInBase[head];
      Node temp = seg.query(min(ps,ph),max(ps,ph)+1);

      ret.maxi   = max(ret.maxi,max(temp.maxi,ret.right+temp.left));
      ret.left   = max(ret.left,ret.value+temp.left);
      ret.right  = max(temp.right,temp.value+ret.right);
      ret.value += temp.value;

      if( f && parent[head] == t ) {
        if( ps < ph ) special = ret.right;
        else          special = ret.left;
      }

      s = parent[head];
    }
  }
  return ret;
}


ll Query(int s,int t,SegmentTree &seg,LCA_RMQ &lca_rmq){
  if( s == t ) {
    int ps = posInBase[s], pt = posInBase[t];
    if( ps > pt ) swap(ps,pt);
    return seg.query(ps,pt+1).maxi;
  }
  int ancestor = lca(s,t,lca_rmq);
  ll temp_maxi = 0;
  DEBUG = true;
  Node a = _Query(s,ancestor,seg,0);
  DEBUG = false;
  temp_maxi += special;
  Node b = _Query(t,ancestor,seg,1);
  temp_maxi += special;
  /*
  cout << "[" << s << "," << ancestor << "," << t << "]" << endl;
  cout << posInBase[s] << " and " << posInBase[t] << endl;
  cout << "special = " << special << endl;
  print(a);
  print(b);
  puts("");
  */

  return max(a.maxi,max(b.maxi,temp_maxi));

  /*
  int ps = posInBase[s], pt = posInBase[t], pa = posInBase[ancestor];
  if( ps <= pa && pa <= pt ) {
    return max(a.maxi,max(b.maxi,a.right+b.left));
  } else if( ps <= pt && pt <= pa ) {
    return max(a.maxi,max(b.maxi,a.right+b.right));
  } else if( pa <= ps && ps <= pt ) {
    return max(a.maxi,max(b.maxi,a.left+b.left));//
  } else if( pa <= pt && pt <= ps ) {
    return max(a.maxi,max(b.maxi,a.right+b.left));
  } else if( pt <= ps && ps <= pa ) {
    return max(a.maxi,max(b.maxi,a.right+b.right));
  } else if( pt <= pa && pa <= ps ) {
    return max(a.maxi,max(b.maxi,a.left+b.right));
  } else assert(false);
  */
}

void _Update(int s,int t,SegmentTree &seg,int c){
  if( s == t ) return seg.update(posInBase[s],posInBase[s]+1,'S',c);
  int chain_s,chain_t=chainID[t];
  while(1){
    chain_s = chainID[s];
    if( chain_s == chain_t ) {
      int ps = posInBase[s], pt = posInBase[t];
      if( ps > pt ) swap(ps,pt);
      seg.update(ps,pt+1,'S',c);
      return;
    } else {
      int head = headID[chain_s];
      int ps = posInBase[s], ph = posInBase[head];
      seg.update(min(ps,ph),max(ps,ph)+1,'S',c);
      s = parent[head];
    }
  }
}


void Update(int s,int t,int c,SegmentTree &seg,LCA_RMQ &lca_rmq){
  if( s == t ) {
    int ps = posInBase[s], pt = posInBase[t];
    if( ps > pt ) swap(ps,pt);
    seg.update(ps,pt+1,'S',c);
    return;
  }
  int ancestor = lca(s,t,lca_rmq);
  _Update(s,ancestor,seg,c);
  _Update(t,ancestor,seg,c);
}


int main(){

  /*
  int N;
  cin >> N;
  vector<int> vec(N);
  rep(i,N) cin >> vec[i];
  SegmentTree seg;
  seg.init(N);
  seg.build(vec);
  while( 1 ){
    int opr,s,t,c;
    cin >> opr >> s >> t;
    if( opr == 0 ) { // set [s,t)
      cin >> c;
      seg.update(s,t,'S',c);
    } else {
      Node node = seg.query(s,t);
      cout << "maxi = " << node.maxi << endl;
      cout << "sum  = " << node.value << endl;
    }
  }
  */
  int Q;
  scanf("%d %d",&V,&Q);
  costs.clear();
  costs.resize(V);
  rep(i,V) scanf("%d",&costs[i]);
  rep(i,V-1) {
    int s,t;
    scanf("%d %d",&s,&t);
    --s, --t;
    G[s].push_back((Edge){t,0});
    G[t].push_back((Edge){s,0});
  }

  HLD_init();
  SegmentTree seg;
  seg.init(V);
  seg.build(baseArray);
  LCA_RMQ lca_rmq;
  LCA_init(V,lca_rmq);


  cout << "baseArray = " << endl;
  rep(i,baseArray.size()) cout << baseArray[i] << " "; cout << endl;
  cout << "chainID = " << endl; 
  rep(i,(int)chainID.size()) cout << chainID[i] << " "; cout << endl;
  cout << "headID = " << endl;
  rep(i,(int)headID.size()) cout << headID[i] << " "; cout << endl;
  cout << "parent = " << endl;
  rep(i,(int)parent.size()) cout << parent[i] << " "; cout << endl;
  cout << "posInBase = " << endl;
  rep(i,posInBase.size()) cout << "[" << i << "," << posInBase[i] << "] "; cout << endl;

  while(1){
  int L,R;
  cin >> L >> R;
  //print(seg.query(min(posInBase[R],posInBase[L]),max(posInBase[L],posInBase[R])+1));
  print(seg.query(L,R+1));
  }

  return 0;





  rep(i,Q){
    int t,a,b,c;
    scanf("%d %d %d %d",&t,&a,&b,&c);
    --a, --b;
    if( t == 1 ) {
      Update(a,b,c,seg,lca_rmq);
    } else if( t == 2 ) {
      printf("%lld\n",Query(a,b,seg,lca_rmq));
    } else assert(false);
    /*
    cout << endl << endl;
    print(seg.query(posInBase[9],posInBase[3]+1));
    cout << endl;
    print(seg.query(posInBase[8],posInBase[8]+1));
    */
  }


	

  return 0;
}