```
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
#define ll long long
#define maxn 200010
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
#define IT set<node>::iterator
using namespace std;
int n, m, c, r, t, x, y, z, num, cnt, sss, fir1, fir2;
int a[maxn], ans[maxn], tag[maxn], depth[maxn], fa[maxn], top[maxn], id[maxn], dd[maxn];
int son[maxn], head[maxn], siz[maxn];
struct hz {
int next;
int to;
}h[maxn];
inline void in(int &x){
x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c==-1) return;
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x=x*f;
}
inline void out(int a){
if(a<0){
a*=-1;
putchar('-');
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}
struct node{
int l;
int r;
mutable int v;
node(int L, int R = -1, int V = 0):l(L), r(R), v(V){}
bool operator <(const node &o)const {
return l < o.l;
}
};
set<node> s;
IT split(int pos) {
IT it = s.lower_bound(node(pos));
if(it != s.end() && it->l == pos)
return it;
--it;
int L = it->l;
int R = it->r;
int V = it->v;
s.erase(it);
s.insert(node(L, pos-1, V));
return s.insert(node(pos, R, V)).first;
}
void assign_val(int l, int r, int val = 0) {
IT itr = split(r+1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, val));
}
int query(int l, int r) {
IT itr = split(r+1), itl = split(l);
int anss = fir1;
int res = fir1;
--itr;
--itl;
for(; itl != itr; --itr) {
res += (itr->r-itr->l+1)*itr->v;
if(res > anss)
anss = res;
if(res < 0)
res = 0;
}
fir1 = res;
return anss;
}
void add(int from, int to) {
h[++num].next = head[from];
h[num].to = to;
head[from] = num;
}
void dfs1(int f, int ff) {
fa[f] = ff;
depth[f] = depth[ff]+1;
siz[f] = 1;
for(re int i = head[f]; i != 0; i = h[i].next) {
if(h[i].to == ff)
continue;
dfs1(h[i].to, f);
siz[f] += siz[h[i].to];
if(siz[h[i].to] > siz[son[f]])
son[f] = h[i].to;
}
}
void dfs2(int x, int topf) {
top[x] = topf;
id[x] = ++cnt;
dd[cnt] = a[x];
if(!son[x])
return;
dfs2(son[x], topf);
for(re int i = head[x]; i != 0; i = h[i].next) {
if(h[i].to == fa[x] || h[i].to == son[x])
continue;
dfs2(h[i].to, h[i].to);
}
}
void updrange(int x, int y, int k) {
while(top[x] != top[y]) {
if(depth[top[x]] < depth[top[y]])
swap(x, y);
assign_val(id[top[x]], id[x], k);
x = fa[top[x]];
}
if(depth[x] > depth[y])
swap(x, y);
assign_val(id[x], id[y], k);
}
int qrange(int x, int y) {
int anss = 0;
while(top[x] != top[y]) {
if(depth[top[x]] < depth[top[y]]) {
swap(x, y);
swap(fir1, fir2);
}
anss = max(anss, query(id[top[x]], id[x]));
x = fa[top[x]];
}
if(depth[x] > depth[y]) {
swap(x, y);
swap(fir1, fir2);
}
anss = max(anss, query(id[x], id[y]));
return anss;
}
//void ts(int l, int r) {
// cout << endl;
// IT itr = split(r+1), itl = split(l);
// for(; itl != itr; --itl)
// FOR(i, 1, itl->r-itl->l+1)
// cout << itl->v << " ";
// cout << endl;
// return;
//}
int main() {
in(n);
FOR(i, 1, n)
in(a[i]);
FOR(i, 1, n-1) {
in(x), in(y);
add(x, y);
add(y, x);
}
dfs1(1, 0);
dfs2(1, 1);
FOR(i, 1, n)
s.insert(node(i, i, dd[i]));
in(m);
FOR(i, 1, m) {
in(t);
if(t == 1) {
in(x), in(y);
fir1 = 0;
fir2 = 0;
out(qrange(x, y));
putchar(10);
}
else {
in(x), in(y), in(z);
updrange(x, y, z);
// ts(1, n);
}
}
}
```
by Juan_feng @ 2018-11-23 09:47:39
做法是树链剖分套珂朵莉树（这时候是不是应该@某位dalao啊
by Juan_feng @ 2018-11-23 09:49:37
这时候应该@[chtholly_tree](/space/show?uid=17850)
by Ynoi @ 2018-11-23 09:49:53
@[树链剖分](/space/show?uid=124721) @您自己可还行
by Juan_feng @ 2018-11-23 09:50:38
别说了，巨佬，蒟蒻先%为敬
by Ophelia @ 2018-11-23 09:52:54
改了一点，然而还是WA
下面是新的qrange，原本的在最后一次统计的时候没有计算链两边的原有值（只算了一边）
```
int qrange(int x, int y) {
int anss = 0;
while(top[x] != top[y]) {
if(depth[top[x]] < depth[top[y]]) {
swap(x, y);
swap(fir1, fir2);
}
anss = max(anss, query(id[top[x]], id[x]));
x = fa[top[x]];
}
if(depth[x] > depth[y]) {
swap(x, y);
swap(fir1, fir2);
}
anss = max(anss, query(id[x], id[y]));
anss = max(anss, fir1+fir2);
return anss;
}
```
by Juan_feng @ 2018-11-23 10:12:20
@[Juan_feng](/space/show?uid=66965) ~~线段树这么优秀为什么要写Chtholly~~
by Itst @ 2018-11-23 10:28:41
@[Juan_feng](/space/show?uid=66965) what
by 斯蒂芬王 @ 2018-11-23 10:38:03
@[斯蒂芬王](/space/show?uid=85793) ？？？
by Juan_feng @ 2018-11-23 15:25:09
@[Itst](/space/show?uid=96296) Orz只是想试试珂朵莉树能不能过
by Juan_feng @ 2018-11-23 15:25:34