hdu5052 Yaoge’s maximum profit 树链剖分

本文主要是介绍hdu5052 Yaoge’s maximum profit 树链剖分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一棵树上，从u走到v，在某点买入，咋之后的某点卖出，求最大利润。

维护正着走和反着走的最大利润。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#define fi first
#define se second
#define pii pair<int,int>
#define ll long long
#define inf 1000000000
#define eps 1e-8
using namespace std;
const int maxn=100005;
int son[maxn],top[maxn],dep[maxn],fa[maxn],siz[maxn],id[maxn],fid[maxn];
int sz;
vector<int>g[maxn];
int val[maxn];
int n,q;
struct Node
{int mi,mx;int ans;int o;Node(int a,int b,int c,int d):mi(a),mx(b),ans(c),o(d){}Node(){}
}node[maxn<<2];
int add[maxn<<2];
void dfs(int u,int f)
{siz[u]=1;son[u]=0;for(int i=0;i<g[u].size();i++) {if(g[u][i]==f)continue;int v=g[u][i];fa[v]=u;dep[v]=dep[u]+1;dfs(v,u);if(siz[v]>siz[son[u]]) son[u]=v;siz[u]+=siz[v];}
}
void build(int u,int w)
{id[u]=++sz;fid[sz]=u;top[u]=w;if(son[u]) build(son[u],w);for(int i=0;i<g[u].size();i++) {int v=g[u][i];if(v==fa[u]) continue;if(v!=son[u]) build(v,v);}
}
void T()
{int rt=(n+1)/2;sz=0;dep[rt]=0;fa[rt]=0;dfs(rt,0);build(rt,rt);
}
void pushUp(int rt)
{node[rt].mx=max(node[rt<<1].mx,node[rt<<1|1].mx);node[rt].mi=min(node[rt<<1].mi,node[rt<<1|1].mi);node[rt].ans=max(node[rt<<1].ans,node[rt<<1|1].ans);node[rt].ans=max(node[rt].ans,node[rt<<1|1].mx-node[rt<<1].mi);node[rt].o=max(node[rt<<1].o,node[rt<<1|1].o);node[rt].o=max(node[rt].o,node[rt<<1].mx-node[rt<<1|1].mi);
}
void pushDown(int rt)
{if(add[rt]==0) return;node[rt<<1].mi+=add[rt];node[rt<<1].mx+=add[rt];node[rt<<1|1].mi+=add[rt];node[rt<<1|1].mx+=add[rt];add[rt<<1]+=add[rt];add[rt<<1|1]+=add[rt];add[rt]=0;
}
void update(int L,int R,int c,int l,int r,int rt)
{if(L<=l&&R>=r) {node[rt].mx+=c;node[rt].mi+=c;add[rt]+=c;return;}pushDown(rt);int m=((l+r)>>1);//Node u={inf,-inf,0};if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,rt<<1|1);pushUp(rt);
}
void update(int a,int b,int c)
{int f1=top[a],f2=top[b];while(f1!=f2) {if(dep[f1]<dep[f2]) {swap(f1,f2);swap(a,b);}update(id[f1],id[a],c,1,n,1);a=fa[f1]; f1=top[a];}if(dep[a]>dep[b]) swap(a,b);update(id[a],id[b],c,1,n,1);
}
Node unite(Node a,Node b)
{Node u;u.mx=max(a.mx,b.mx);u.mi=min(a.mi,b.mi);u.ans=max(a.ans,b.ans);u.ans=max(u.ans,b.mx-a.mi);u.o=max(a.o,b.o);u.o=max(u.o,a.mx-b.mi);return u;
}
Node query(int L,int R,int l,int r,int rt)
{if(L<=l&&R>=r)return node[rt];pushDown(rt);Node u=Node(inf,-inf,0,0);int m=((l+r)>>1);if(L<=m)u=unite(u,query(L,R,l,m,rt<<1));if(R>m)u=unite(u,query(L,R,m+1,r,rt<<1|1));pushUp(rt);return u;
}
int query(int u,int v)
{int a = top[u], b = top[v];Node lpath = Node(inf , -inf, 0,0), rpath = Node(inf, -inf, 0,0);while(a != b){if( dep[a] > dep[b]){Node res = query(id[a], id[u],1,n,1);//cout<<res.mi<<" "<<res.mx<<" "<<res.ans<<endl;swap(res.ans, res.o);lpath = unite(lpath, res);u = fa[a];a = top[u];}else{Node res = query(id[b], id[v],1,n,1);//cout<<res.mi<<" "<<res.mx<<" "<<res.ans<<endl;rpath = unite(res, rpath);v = fa[b];b = top[v];}}Node ans;if( dep[u] < dep[v] ){ans = query(id[u], id[v],1,n,1);}else{ans = query(id[v], id[u],1,n,1);swap(ans.ans,ans.o);}ans = unite(lpath, ans);ans = unite(ans, rpath);return ans.ans;
}
void buildTree(int l,int r,int rt)
{add[rt]=0;if(l==r) {int a=fid[l];node[rt].mi=node[rt].mx=val[a];node[rt].ans=node[rt].o=0;return;}int m=((l+r)>>1);buildTree(l,m,rt<<1);buildTree(m+1,r,rt<<1|1);pushUp(rt);
}
int main()
{int t;int a,b,c;scanf("%d",&t);while(t--) {scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&val[i]);g[i].clear();}for(int i=0;i<n-1;i++) {scanf("%d%d",&a,&b);g[a].push_back(b);g[b].push_back(a);}T();buildTree(1,n,1);//cout<<node[1].mi<<" "<<node[1].mx<<" "<<node[1].ans<<endl;scanf("%d",&q);while(q--) {scanf("%d%d%d",&a,&b,&c);printf("%d\n",query(a,b));update(a,b,c);}}return 0;
}

这篇关于hdu5052 Yaoge’s maximum profit 树链剖分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---