codevs3305 水果姐逛水果街Ⅱ

codevs3305 水果姐逛水果街Ⅱ

​​ 题目描述 Description

水果姐第二天心情也很不错，又来逛水果街。

突然，cgh又出现了。cgh施展了魔法，水果街变成了树结构（店与店之间只有一条唯一的路径）。

同样还是n家水果店，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。

cgh给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去。求最多可以赚多少钱。

水果姐向学过oi的你求助。

输入描述 Input Description 第一行n，表示有n家店

下来n个正整数，表示每家店一个苹果的价格。

下来n-1行，每行两个整数x，y，表示第x家店和第y家店有一条边。

下来一个整数m，表示下来有m个询问。

下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。

输出描述 Output Description 有m行。

每行对应一个询问，一个整数，表示面对cgh的每次询问，水果姐最多可以赚到多少钱。

样例输入 Sample Input 10 16 5 1 15 15 1 8 9 9 15 1 2 1 3 2 4 2 5 2 6 6 7 4 8 1 9 1 10 6 9 1

5 1 1 7 3 3 1 1 3 6

样例输出 Sample Output 7 11 7 0 0 15

数据范围及提示 Data Size & Hint

0<=苹果的价格<=10^8

0< n<=200000

0< m<=10000

思路：同tjoi2015旅游见蒟蒻我的blog tjoi2015旅游

#include#include#define N 220000#define inf 0x7fffffffusing namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int y,next;}data[N<<1];struct node1{ int max,min,ans,ans1; node1(){ ans=ans1=max=0;min=inf; }};struct node2{ int l,r,left,right,max,min,ans,ans1,lazy;}tree[N<<2];int size[N],id[N],fa[N],son[N],tp[N],a[N],dep[N],h[N],cnt,root,n,num,m,w[N];void dfs1(int x){ size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if(fa[x]==y) continue; dep[y]=dep[x]+1;fa[y]=x;dfs1(y);size[x]+=size[y]; if (size[y]>size[son[x]]) son[x]=y; }}void dfs2(int x,int top){ id[x]=++cnt;tp[x]=top;w[cnt]=a[x]; if (son[x]) dfs2(son[x],top); for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (y==fa[x]||y==son[x]) continue; dfs2(y,y); }}inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].ans=max(tree[r].max-tree[l].min,max(tree[l].ans,tree[r].ans)); tree[x].ans1=max(tree[l].max-tree[r].min,max(tree[l].ans1,tree[r].ans1)); tree[x].min=min(tree[l].min,tree[r].min); tree[x].max=max(tree[l].max,tree[r].max);}void print(int x){ if (tree[x].left) print(tree[x].left); printf("%d %d %d %d %d %d %d\n",tree[x].l,tree[x].r,tree[x].max,tree[x].min,tree[x].ans,tree[x].ans1,tree[x].lazy); if (tree[x].right) print(tree[x].right);}void build(int &x,int l,int r){ x=++cnt;tree[x].l=l;tree[x].r=r; if(l==r){ tree[x].min=tree[x].max=w[l]; tree[x].ans=tree[x].ans1=0;return; } int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}node1 update1(node1 tmp1,node1 tmp2){ node1 ans1; ans1.ans=max(tmp2.max-tmp1.min,max(tmp1.ans,tmp2.ans)); ans1.ans1=max(tmp1.max-tmp2.min,max(tmp1.ans1,tmp2.ans1)); ans1.min=min(tmp1.min,tmp2.min); ans1.max=max(tmp1.max,tmp2.max); return ans1;}void pushdown(int x){ if (!tree[x].lazy) return; int l=tree[x].left,r=tree[x].right; int lazy=tree[x].lazy; tree[l].lazy+=lazy;tree[r].lazy+=lazy; tree[l].max+=lazy;tree[r].max+=lazy; tree[l].min+=lazy;tree[r].min+=lazy; tree[x].lazy=0;}node1 query(int rt,int l,int r,int v){ if(l<=tree[rt].l&&r>=tree[rt].r){ tree[rt].lazy+=v;tree[rt].max+=v;tree[rt].min+=v; node1 tmp;tmp.max=tree[rt].max;tmp.min=tree[rt].min;tmp.ans=tree[rt].ans;tmp.ans1=tree[rt].ans1; return tmp; } int mid=(tree[rt].l+tree[rt].r)>>1; node1 tmp1;node1 tmp2;pushdown(rt); if (l<=mid) tmp1=query(tree[rt].left,l,r,v); if (r>mid) tmp2=query(tree[rt].right,l,r,v); update(rt); return update1(tmp1,tmp2);}inline void swap(int &x,int &y){ x^=y;y^=x;x^=y;}void solve(int x,int y,int v){ node1 ansl,ansr; while (tp[x]!=tp[y]){ if(dep[tp[x]]>dep[tp[y]]){ ansl=update1(ansl,query(root,id[tp[x]],id[x],v)); x=fa[tp[x]]; }else{ ansr=update1(query(root,id[tp[y]],id[y],v),ansr); y=fa[tp[y]]; } } swap(ansl.ans,ansl.ans1); if (id[x]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。