题解 SP6779 【GSS7 - Can you answer these queries VII】
Juan_feng
2018-11-24 11:26:33
### NOIP之后无心刷DP题，就又来水数据结构了= =
#### 本题可以用树剖+珂朵莉树水过
**如果不了解珂朵莉树的话可以到[CF896C](https://www.luogu.org/problemnew/show/CF896C)的题解区看一下**
具体做法就是先用树剖处理一下，然后区间修改就用珂朵莉树暴力推平，区间最大子段和直接暴力去求就好啦qwq
注意一下在树剖求区间最大子段和，每次统计的时候要加上之前剩余数值（前一条链上的与当前链相连的最大子段和，因为是x， y两边同时向上跳，所以要用两个变量去保存），交换x， y的时候要同时交换对应的剩余数值，**当最后x， y在同一条链上的时候要再交换一下x，y对应的剩余数值**。（WA了好几次QAQ）
**如果有什么问题或者对题解有什么意见和建议的话欢迎私信小蒟蒻qwqwq。**
**那么代码如下：**
```
#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); //注意
}
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);
add(x, y);
add(y, x);
}
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);
}
}
}
```