国外企业招聘网站,专门做外贸的网站有哪些,网页搜索引擎优化技术,重庆规模最大的建网站公司BZOJ3999: [TJOI2015]旅游 Description 为了提高智商#xff0c;ZJY准备去往一个新世界去旅游。这个世界的城市布局像一棵树。每两座城市之间只有一条路径可以互达。每座城市都有一种宝石#xff0c;有一定的价格。ZJY为了赚取最高利益#xff0c;她会选择从A城市买入再转手…BZOJ3999: [TJOI2015]旅游 Description 为了提高智商ZJY准备去往一个新世界去旅游。这个世界的城市布局像一棵树。每两座城市之间只有一条路径可 以互达。每座城市都有一种宝石有一定的价格。ZJY为了赚取最高利益她会选择从A城市买入再转手卖到B城市 。由于ZJY买宝石时经常卖萌因而凡是ZJY路过的城市这座城市的宝石价格会上涨。让我们来算算ZJY旅游完之 后能够赚取的最大利润。如a城市宝石价格为v则ZJY出售价格也为v Input 第一行输入一个正整数N表示城市个数。 接下来一行输入N个正整数表示每座城市宝石的最初价格p每个宝石的初始价格不超过100。 第三行开始连续输入N-1行每行有两个数字x和y。表示x城市和y城市有一条路径。城市编号从1开始。 下一行输入一个整数Q表示询问次数。 接下来Q行每行输入三个正整数a,b,v表示ZJY从a旅游到b城市宝石上涨v。 1≤ N≤50000 1≤Q ≤50000 Output 对于每次询问输出ZJY可能获得的最大利润如果亏本则输出0。 Sample Input 3 1 2 3 1 2 2 3 2 1 2 100 1 3 100 Sample Output 1 1 题解Here! 额相信大部分人肯定没有一遍读懂题意。。。 本蒟蒻也是看别的巨佬的博客弄懂的。。。 出题人语文水平真差。。。 其实就是求从$x$到$y$的有向路径上任意两个点的最大差值。 如果这只是一道线段树题还是十分简单的 对于一个区间其路径最大差值为 $$\max \left( \text{右儿子最大差值,左儿子最大差值,(右儿子MAX-左儿子MIN)或者(左儿子MAX-右儿子MIN)} \right)$$ 对于这样的要返回多权值的问题线段树传递结构体比较容易。这是链上的情况。然后我们要求的是树的情况。 辣就用树链剖分在$O(\log_2n)$的时间内转换成链上的情况就好了嘛。。。 注意到要解决好一个方向怎么把控的问题。因为我们在树剖一步一步一步往上爬的时候从询问起点往上爬和询问终点往上爬是不一样的我的处理方式是每次都进行判断是线段树左到右还是右到左扫最大差值之后将每段区间内的$\min$和$\max$记录下来即分别开两个数组从起点爬的和终点爬的。 之后再将这一大段区间的$\min$和$\max$连接成一条链直接暴力跑一次区间最大差值得到最大答案就是了。说得容易真的写得很恶心啊 附上将近$200$行的代码 #includeiostream
#includealgorithm
#includecstdio
#define LSON rt1
#define RSON rt1|1
#define MAXSUM(x) b[x].maxn
#define MINSUM(x) b[x].minn
#define MAXL(x) b[x].maxl
#define MAXR(x) b[x].maxr
#define SIGN(x) b[x].c
#define LSIDE(x) b[x].l
#define RSIDE(x) b[x].r
#define WIDTH(x) (RSIDE(x)-LSIDE(x)1)
#define MAXN 50010
#define MAX (1LL62)
using namespace std;
int n,m,c1,d1;
int val[MAXN],head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],id[MAXN],pos[MAXN],top[MAXN];
long long min_x[MAXN],max_x[MAXN],min_y[MAXN],max_y[MAXN];
struct Tree{int next,to;
}a[MAXN1];
struct Segment_Tree{long long maxn,minn,maxl,maxr,c;int l,r;
}b[MAXN2];
inline int read(){int date0,w1;char c0;while(c0||c9){if(c-)w-1;cgetchar();}while(c0c9){datedate*10c-0;cgetchar();}return date*w;
}
inline long long max(const long long x,const long long y){return xy?x:y;}
inline long long min(const long long x,const long long y){return xy?x:y;}
inline void add(int x,int y){a[c].toy;a[c].nexthead[x];head[x]c;a[c].tox;a[c].nexthead[y];head[y]c;
}
void dfs1(int rt){son[rt]0;size[rt]1;for(int ihead[rt];i;ia[i].next){int willa[i].to;if(!deep[will]){deep[will]deep[rt]1;fa[will]rt;dfs1(will);size[rt]size[will];if(size[son[rt]]size[will])son[rt]will;}}
}
void dfs2(int rt,int f){id[rt]d;pos[id[rt]]rt;top[rt]f;if(son[rt])dfs2(son[rt],f);for(int ihead[rt];i;ia[i].next){int willa[i].to;if(will!fa[rt]will!son[rt])dfs2(will,will);}
}
inline void pushup(int rt){MAXSUM(rt)max(MAXSUM(LSON),MAXSUM(RSON));MINSUM(rt)min(MINSUM(LSON),MINSUM(RSON));MAXL(rt)max(MAXSUM(RSON)-MINSUM(LSON),max(MAXL(LSON),MAXL(RSON)));MAXR(rt)max(MAXSUM(LSON)-MINSUM(RSON),max(MAXR(LSON),MAXR(RSON)));
}
inline void pushdown(int rt){if(!SIGN(rt)||LSIDE(rt)RSIDE(rt))return;SIGN(LSON)SIGN(rt);MAXSUM(LSON)SIGN(rt);MINSUM(LSON)SIGN(rt);SIGN(RSON)SIGN(rt);MAXSUM(RSON)SIGN(rt);MINSUM(RSON)SIGN(rt);SIGN(rt)0;
}
void buildtree(int l,int r,int rt){LSIDE(rt)l;RSIDE(rt)r;SIGN(rt)0;if(lr){MAXSUM(rt)MINSUM(rt)val[pos[l]];MAXL(rt)MAXR(rt)0;return;}int midlr1;buildtree(l,mid,LSON);buildtree(mid1,r,RSON);pushup(rt);
}
void update(int l,int r,long long c,int rt){if(lLSIDE(rt)RSIDE(rt)r){SIGN(rt)c;MAXSUM(rt)c;MINSUM(rt)c;return;}pushdown(rt);int midLSIDE(rt)RSIDE(rt)1;if(lmid)update(l,r,c,LSON);if(midr)update(l,r,c,RSON);pushup(rt);
}
Segment_Tree query(int l,int r,int c,int rt){if(lLSIDE(rt)RSIDE(rt)r)return b[rt];pushdown(rt);int midLSIDE(rt)RSIDE(rt)1;if(rmid)return query(l,r,c,LSON);if(midl)return query(l,r,c,RSON);Segment_Tree ans,lson,rson;lsonquery(l,r,c,LSON);rsonquery(l,r,c,RSON);ans.maxnmax(lson.maxn,rson.maxn);ans.minnmin(lson.minn,rson.minn);if(c1)ans.maxrmax(lson.maxn-rson.minn,max(lson.maxr,rson.maxr));elseans.maxlmax(rson.maxn-lson.minn,max(lson.maxl,rson.maxl));return ans;
}
void update_path(int x,int y,long long k){while(top[x]!top[y]){if(deep[top[x]]deep[top[y]])swap(x,y);update(id[top[x]],id[x],k,1);xfa[top[x]];}if(deep[x]deep[y])swap(x,y);update(id[x],id[y],k,1);
}
void solve(int x,int y){int top_x0,top_y0;long long ans0;Segment_Tree s;while(top[x]!top[y]){if(deep[top[x]]deep[top[y]]){squery(id[top[x]],id[x],1,1);ansmax(ans,s.maxr);top_x;min_x[top_x]s.minn;max_x[top_x]s.maxn;xfa[top[x]];}else{squery(id[top[y]],id[y],2,1);ansmax(ans,s.maxl);top_y;min_y[top_y]s.minn;max_y[top_y]s.maxn;yfa[top[y]];}}if(deep[x]deep[y]){squery(id[y],id[x],1,1);ansmax(ans,s.maxr);top_x;min_x[top_x]s.minn;max_x[top_x]s.maxn;}else{squery(id[x],id[y],2,1);ansmax(ans,s.maxl);top_y;min_y[top_y]s.minn;max_y[top_y]s.maxn;}for(int itop_y;i1;i--){top_x;min_x[top_x]min_y[i];max_x[top_x]max_y[i];}long long maxn-MAX,minnMAX;for(int i1;itop_x;i){ansmax(ans,max_x[i]-minn);minnmin(minn,min_x[i]);}for(int itop_x;i1;i--){ansmax(ans,maxn-min_x[i]);maxnmax(maxn,max_x[i]);}if(ans0)printf(0\n);else printf(%lld\n,ans);
}
void work(){int x,y,k;while(m--){xread();yread();kread();solve(x,y);update_path(x,y,k);}
}
void init(){int x,y;nread();for(int i1;in;i)val[i]read();for(int i1;in;i){xread();yread();add(x,y);}mread();deep[1]1;dfs1(1);dfs2(1,1);buildtree(1,n,1);
}
int main(){init();work();return 0;
}转载于:https://www.cnblogs.com/Yangrui-Blog/p/9562845.html
