初步判定查询部分写错了，但是蒟蒻太菜，看不出来
by 马峰 @ 2018-10-18 10:42:53
强
by Star_gazer @ 2018-10-18 10:57:22
哦我的整体查询的部分写错了，但是改了之后依然哇哇大哭，求助各位神犇
```
#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
int x=0,gf=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') gf=-1;c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;c=getchar();
}
return x*gf;
}
struct Edge{
int x,y,nxt;
}edge[100010];
int n,a[100010],tot,head[100010];
void add(int x,int y){
edge[++tot].x=x,edge[tot].y=y,edge[tot].nxt=head[x];head[x]=tot;
}
//树剖
int cnt,id[100010];
struct Node{
int fa,w=1,depth,son=-1,top;
}node[100010];
void dfs(int x){
for(int i=head[x];i;i=edge[i].nxt){
int v=edge[i].y;
if(v==node[x].fa) continue;
node[v].fa=x;
node[v].depth=node[x].depth+1;
dfs(v);
node[x].w+=node[v].w;
if(node[v].w>node[node[x].son].w||node[x].son==-1) node[x].son=v;
}
}
void dfs2(int x,int top){
//cout<<x<<" "<<top<<endl;
node[x].top=top;id[x]=++cnt;
if(node[x].son==-1) return;
dfs2(node[x].son,top);
for(int i=head[x];i;i=edge[i].nxt){
int v=edge[i].y;
if(v==node[x].fa||v==node[x].son) continue;
dfs2(v,v);
}
}
//线段树
int lazy[400010];
struct Segement_tree{
int front=0,back=0,mid=0,sum=0;
}tree[400010];
void push_up(int o){
tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum;
tree[o].mid=max(tree[o<<1].mid,max(tree[o<<1|1].mid,tree[o<<1].back+tree[o<<1|1].front));
tree[o].front=max(tree[o<<1].front,tree[o<<1].sum+tree[o<<1|1].front);
tree[o].back=max(tree[o<<1].back,tree[o<<1|1].sum+tree[o].back);
}
void build(int o,int l,int r){
if(l==r) {
tree[o].sum=tree[o].mid=tree[o].front=tree[o].back=max(0,a[id[l]]);tree[o].sum=a[id[l]];
}
else{
int mid=(l+r)>>1;
build(o<<1,l,mid);build(o<<1|1,mid+1,r);
push_up(o);
}
}
void push_down(int o,int l,int r){
int mid=(l+r)>>1;
lazy[o<<1]=lazy[o<<1|1]=lazy[o];
tree[o<<1].mid=tree[o<<1].front=tree[o<<1].back=max(0,lazy[o<<1]*(mid-l+1));tree[o<<1].sum=lazy[o<<1]*(mid-l+1);
tree[o<<1|1].mid=tree[o<<1|1].front=tree[o<<1|1].back=max(0,lazy[o<<1|1]*(r-mid));tree[o<<1|1].sum=lazy[o<<1|1]*(r-mid);
lazy[o]=0;
}
void update(int o,int l,int r,int ql,int qr,int u){
if(l>=ql&&r<=qr){
lazy[o]=u;tree[o].mid=tree[o].front=tree[o].back=max(0,u*(r-l+1));tree[o].sum=u*(r-l+1);return;
}
if(lazy[o])push_down(o,l,r);
int mid=(l+r)>>1;
if(mid>=ql) update(o<<1,l,mid,ql,qr,u);
if(mid<qr) update(o<<1|1,mid+1,r,ql,qr,u);
push_up(o);
}
Segement_tree query(int o,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr) return tree[o];
if(lazy[o])push_down(o,l,r);
int mid=(l+r)>>1;
Segement_tree dhy,mxg;bool flag=0,flag1=0;
if(mid>=ql) dhy=query(o<<1,l,mid,ql,qr),flag=1;
if(mid<qr) mxg=query(o<<1|1,mid+1,r,ql,qr),flag1=1;
if(flag&&flag1){
Segement_tree ans;
ans.sum=dhy.sum+mxg.sum;
ans.front=max(dhy.front,dhy.sum+mxg.front);
ans.back=max(mxg.back,dhy.back+mxg.sum);
ans.mid=max(max(mxg.mid,dhy.mid),mxg.front+dhy.back);
return ans;
}
if(flag) return dhy;
return mxg;
}
//直接查询
Segement_tree operator +(const Segement_tree& a,const Segement_tree &b){
Segement_tree tmp;
tmp.mid=max(a.mid,max(b.mid,a.back+b.front));
tmp.sum=a.sum+b.sum;
tmp.front=max(a.front,a.sum+b.front);
tmp.back=max(a.back+b.sum,b.back);
return tmp;
}
Segement_tree tquery(int x,int y){
// x=id[x],y=id[y];
Segement_tree ansx,ansy;
while(node[x].top!=node[y].top){
if(node[node[x].top].depth<node[node[y].top].depth){
ansy=query(1,1,n,id[node[y].top],id[y])+ansy;y=node[node[y].top].fa;
}
else{
ansx=query(1,1,n,id[node[x].top],id[x])+ansx;x=node[node[x].top].fa;
}
}
if(id[x]<id[y]) ansy=query(1,1,n,id[x],id[y])+ansy;
else ansx=query(1,1,n,id[y],id[x])+ansx;
Segement_tree tmp;tmp.mid=max(ansx.back+ansy.front,max(ansx.mid,ansy.mid));
return tmp;
}
void tupdate(int x,int y,int u){
// x=id[x],y=id[y];
while(node[x].top!=node[y].top){
if(node[node[x].top].depth<node[node[y].top].depth) swap(x,y);
update(1,1,n,id[node[x].top],id[x],u);
x=node[node[x].top].fa;
}
if(node[x].depth>node[y].depth) swap(x,y);
update(1,1,n,id[x],id[y],u);
}
int main(){
freopen("qwq.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n-1;i++){
int x,y;x=read();y=read();add(x,y);add(y,x);
}
dfs(1);
dfs2(1,1);//for(int i=1;i<=n;i++) cout<<id[i]<<" ";system("pause");
int q=read();
build(1,1,n);
while(q--){
//cout<<query(1,1,n,1,3).sum<<endl;
int opt,a,b;
opt=read(),a=read(),b=read();
if(opt==1){
cout<<tquery(a,b).mid<<'\n';
}
else{
int c;c=read();tupdate(a,b,c);
}
}
return 0;
}
```
by 马峰 @ 2018-10-18 11:10:11
刚学OI就会树剖线段树，TQL
by DefFrancis @ 2018-10-18 11:12:28
@[DefFrancis](/space/show?uid=46750) 菜菜快崩溃了，dalao不要来嘲讽了
by 马峰 @ 2018-10-18 11:13:05
@[马峰](/space/show?uid=80434) 为什么贵校假到飞起啊
by DefFrancis @ 2018-10-18 11:14:21
@[DefFrancis](/space/show?uid=46750) 为什么贵校也假到起飞啊
by 马峰 @ 2018-10-18 11:15:27
noip不考 下一个
by Rainy_chen @ 2018-10-18 11:16:44
DefFrancis 虽然是神犇，但是他嘲讽蒟蒻的语气确实令人不悦啊 @[马峰](/space/show?uid=80434)
by misinclair @ 2018-10-18 11:27:08
@[AK_583](/space/show?uid=46749) 对啊
by 马峰 @ 2018-10-18 11:43:20