SP6779 GSS7 - Can you answer these queries VII

Given a tree with N (_N_

first line consists one interger N. next line consists N interger x\_i. next N-1 line , each consists two interger u,v , means that node u and node v are connected next line consists 1 interger Q. next Q line : _1 a b_ or _2 a b c_ .

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