# 一无所|知的小|J f

### 题解 SP6779 【GSS7 - Can you answer these queries VII】

posted on 2018-11-24 11:26:33 | under 题解 |

### NOIP之后无心刷DP题，就又来水数据结构了= =

#### 本题可以用树剖+珂朵莉树水过

#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];

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].to = to;
}

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); //注意
}
swap(fir1, fir2); //最后要再交换一下
anss = max(anss, query(id[x], id[y]));
anss = max(anss, fir1+fir2);
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);
}
dfs1(1, 0);
dfs2(1, 1);
FOR(i, 1, n)
s.insert(node(i, i, dd[i]));
s.insert(node(1, n+233, 0));
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);
}
}
}