hdu5052 Yaoge’s maximum profit 树链剖分

2024-08-26 13:58

本文主要是介绍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 树链剖分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1108754

相关文章

leetcode#628. Maximum Product of Three Numbers

题目 Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3]Output: 6 Example 2: Input: [1,2,3,4]Output: 24 Note: The lengt

Maximum likelihood function maximizes what thing?

最大似然函数(Maximum Likelihood Function)最大化的是数据在给定参数下出现的概率。具体来说,它最大化的是似然函数(Likelihood Function),即给定参数 ( \theta ) 下观测数据的概率。在统计学中,似然函数 ( L(\theta) ) 通常定义为所有独立观测数据点概率的乘积,对于参数 ( \theta ) 的函数。 对于一组独立同分布的观测数据

ORA-24067: exceeded maximum number of subscribers for queue ADMIN.SMS_MT_QUEUE

临时处理办法: delete from aq$_ss_MT_tab_D;delete from aq$_ss_MT_tab_g;delete from aq$_ss_MT_tab_h;delete from aq$_ss_MT_tab_i;delete from aq$_ss_MT_tab_p;delete from aq$_ss_MT_tab_s;delete from aq$

[LeetCode] 239. Sliding Window Maximum

题:https://leetcode.com/problems/sliding-window-maximum/description/ 题目 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You

【论文分享】GPU Memory Exploitation for Fun and Profit 24‘USENIX

目录 AbstractIntroductionResponsible disclosure BackgroundGPU BasicsGPU architectureGPU virtual memory management GPU Programming and ExecutionGPU programming modelGPU kernelDevice function NVIDIA

vue3 el-menu 菜单Maximum recursive updates exceeded 报错

vue3 用el-menu实现管理后台左侧菜单,报Uncaught (in promise) Maximum recursive updates exceeded in component <ElMenu>. This means you have a reactive effect that is mutating its own dependencies and thus recursivel

树链剖分 + 后缀数组 - E. Misha and LCP on Tree

E. Misha and LCP on Tree  Problem's Link   Mean:  给出一棵树,每个结点上有一个字母。每个询问给出两个路径,问这两个路径的串的最长公共前缀。 analyse: 做法:树链剖分+后缀数组. 记录每条链的串,正反都需要标记,组成一个长串. 然后记录每条链对应的串在大串中的位置,对大串求后缀数组,最后询问就是在一些链

【HDU】5029 Relief grain 树链剖分+离线标记法

传送门:【HDU】5029 Relief grain 题目分析:这题的方法太美妙了! 首先看到这是一颗树,那么很容易想到树链剖分。然后想到可以将查询排个序,然后每一种查询执行完以后更新每个点的最优值。但是这样进行的复杂度太高!尤其是当z给的没有一样的时候尤其如此。 那么我们是否可以找到更加高效的算法? 答案是肯定的! 先简化一下问题,如果这些操作是在线段上进行的,我们怎么求解?

【HDU】5221 Occupation【树链剖分】

传送门:【HDU】5221 Occupation 题目分析: 最直接的想法,用一棵树链剖分维护路径,一棵dfs序线段树维护子树。因为每次最多修改一个点,所以修改的时候我们暴力修改每个点就可以了。 my  code: my~~code: #pragma comment(linker, "/STACK:102400000,102400000")#include <stdio.h>#in

【HDU】5436 Transmigration tree【树链剖分+dp+rmq】

题目链接:【HDU】5436 Transmigration tree #pragma comment(linker, "/STACK:16777216")#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std ;typedef long long LL ;