[TJOI 2015] 旅游

题目描述：

树上可修改的两点间有序差值最大值…

题目分析：

线段树先分别维护 两个方向的差值最大值
把所有链记录下来
答案要么在一段内，要么最值分别分布在两段内
我们就用每一段的答案更新答案，再单独拿出所有的剖出的链，考虑相互影响来更新答案

题目链接：

Luogu 3976
COGS 1978
BZOJ 3999

Ac 代码：

#include 
#include 
#include 
#include 
#include 
#define ls (o<<1)
#define rs (o<<1)|1
const int maxm=101000;
int head[maxm],to[maxm<<1],net[maxm<<1],cnt;
int fa[maxm],siz[maxm],deep[maxm],son[maxm],top[maxm],id[maxm],rank[maxm],tot;
int val[maxm],n,m;
struct node{int maxx,minx,d1,d2;
};
inline void addedge(int u,int v){to[++cnt]=v,net[cnt]=head[u],head[u]=cnt;}
void dfs1(int now)
{siz[now]=1;for(int i=head[now];i;i=net[i])if(to[i]!=fa[now]){deep[to[i]]=deep[now]+1;fa[to[i]]=now;dfs1(to[i]);siz[now]+=siz[to[i]];if(siz[son[now]]void dfs2(int now,int topx)
{rank[id[now]=++tot]=now;top[now]=topx;if(son[now]) dfs2(son[now],topx);for(int i=head[now];i;i=net[i])if(!id[to[i]]) dfs2(to[i],to[i]);
}
int maxx[maxm<<2],minx[maxm<<2],d1[maxm<<2],d2[maxm<<2],tag[maxm<<2];
void pushup(int o)
{maxx[o]=std::max(maxx[ls],maxx[rs]);minx[o]=std::min(minx[ls],minx[rs]);d1[o]=std::max(std::max(d1[ls],d1[rs]),maxx[rs]-minx[ls]);d2[o]=std::max(std::max(d2[ls],d2[rs]),maxx[ls]-minx[rs]);
}
void pushdown(int o)
{if(tag[o]){maxx[ls]+=tag[o];minx[ls]+=tag[o];tag[ls]+=tag[o];maxx[rs]+=tag[o];minx[rs]+=tag[o];tag[rs]+=tag[o];tag[o]=0;}
}
void build(int o,int l,int r)
{if(l>=r){maxx[o]=minx[o]=val[rank[l]];return;}int mid=(l+r)>>1;build(ls,l,mid),build(rs,mid+1,r);pushup(o);
}
void modify(int o,int l,int r,int ql,int qr,int v)
{if(ql<=l&&r<=qr){maxx[o]+=v;minx[o]+=v;tag[o]+=v;return;}pushdown(o);int mid=(l+r)>>1;if(mid>=ql) modify(ls,l,mid,ql,qr,v);if(mid1,r,ql,qr,v);pushup(o);
}
node ask(int o,int l,int r,int ql,int qr)
{if(ql<=l&&r<=qr) return (node){maxx[o],minx[o],d1[o],d2[o]};pushdown(o);int mid=(l+r)>>1;if(mid>=qr) return ask(ls,l,mid,ql,qr);if(midreturn ask(rs,mid+1,r,ql,qr);node t1=ask(ls,l,mid,ql,qr),t2=ask(rs,mid+1,r,ql,qr);return (node){std::max(t1.maxx,t2.maxx),std::min(t1.minx,t2.minx),std::max(std::max(t1.d1,t2.d1),t2.maxx-t1.minx),std::max(std::max(t1.d2,t2.d2),t1.maxx-t2.minx)};
}
int _top[2];
node stk[2][201],e[402];
std::queue  dl;
inline int asktree(int u,int v,int w)
{int p=0,ans=0;_top[0]=_top[1]=0;while(top[u]!=top[v]){if(deep[top[u]]std::swap(u,v),p^=1;modify(1,1,n,id[top[u]],id[u],w);stk[p][++_top[p]]=ask(1,1,n,id[top[u]],id[u]);u=fa[top[u]];}if(deep[u]std::swap(u,v),p^=1;modify(1,1,n,id[v],id[u],w);stk[p][++_top[p]]=ask(1,1,n,id[v],id[u]);for(int i=1;i<=_top[0];i++){dl.push(stk[0][i]);ans=std::max(ans,stk[0][i].d2);}for(int i=_top[1];i>=1;i--){dl.push(stk[1][i]);ans=std::max(ans,stk[1][i].d1);}int nowmin=0x7fffffff;while(!dl.empty()){node now=dl.front();dl.pop();ans=std::max(ans,now.maxx-nowmin);nowmin=std::min(nowmin,now.minx);}return ans<0?0:ans;
}
int main()
{//freopen("tjoi2015_travel.in","r",stdin);//freopen("tjoi2015_travel.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&val[i]);for(int i=1;iint u,v;scanf("%d%d",&u,&v);addedge(u,v),addedge(v,u);}dfs1(1),dfs2(1,1);scanf("%d",&m);build(1,1,n);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);printf("%d\n",asktree(u,v,w));}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！