[unknown OJ] ZZH的旅行

一、题目

点此看题

二、解法

设 $dp[i]$ 为 $i$ 点的最大有趣度，转移很显然啊：
$$dp[i]=dp[j]+(a[i]+d[i]-d[j])b[j](j\in so{n}_i)$$然后这个柿子是 $O(n^2)$ 的，一眼望过去肯定的决策单调性之类的题了，可以尝试斜率优化：
$$dp[j]+(a[i]+d[i]-d[j])b[j]>dp[k]+(a[i]+d[i]-d[k])b[k]$$$$\frac{dp[j]-d[j]b[j]-dp[k]+d[k]b[k]}{b[j]-b[k]}>-(a[i]+d[i])$$但是由于 $b$ 没有单调性，所以要用平衡树维护凸包，还要启发式合并，所以时间复杂度 $O(n{\log }^{2}n)$

其实上面就足以通过此题了，但十分难写，这里不妨再介绍一种李超树的做法。

大家都知道李超树是维护一次函数之类的，我们不妨把问题这样转化：在 $i$ 的子树中维护若干条直线：$y=b[j]x+dp[j]-d[j]b[j]$，我们要求的是 $x=a[i]+d[i]$ 处最大的 $y$ 值，那么就是李超树板题了：跟线段游戏一模一样。

这次我还想说的是复杂度证明，咋看上去还是要启发式合并和插入，那么不是 $O(n{\log }^{2}n)$ 的吗？其实不然，因为我们维护的是直线，所以相当于是对全局进行修改，知道李超树修改方式的同学就知道这一部分是 $O(n\log n)$ 的。

但启发式合并中不是还要套上插入吗，这里我们就需要用到全局的思想，因为李超树下传之后会砍掉一半，所以总的修改次数是 $O(n\log n)$，这和启发式合并的 $O(n\log n)$ 是相互独立的，所以总的复杂度是 $O(n\log n)$ 。$\mathtt{b}\mathtt{t}\mathtt{w},$ 线段树合并因为话多少个 $O(1)$ 就减少了多少个点，所以时间复杂度才是 $O(n\log n)$ 的

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int M = 1000005;
const int N = 20000005;
const int inf = 2e18;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,tot,cnt,f[M],a[M],b[M],d[M],rt[M],dp[M],p[M],ls[N],rs[N];
struct node
{
	int k,b;
	node(int K=0,int B=-inf) : k(K) , b(B) {}
	int ask(int x)
	{
		return x*k+b;
	}
}tr[N];
struct edge
{
	int v,c,next;
	edge(int V=0,int C=0,int N=0) : v(V) , c(C) , next(N) {}
}e[2*M];
void insert(int &x,int l,int r,node b)
{
	if(b.ask(p[l])==-inf) return ;
	if(!x) x=++cnt;
	int mid=(l+r)>>1;
	if(b.ask(p[mid])>tr[x].ask(p[mid]))
	{
		if(tr[x].ask(p[l])>b.ask(p[l])) insert(ls[x],l,mid,tr[x]);
		if(tr[x].ask(p[r])>b.ask(p[r])) insert(rs[x],mid+1,r,tr[x]); 
		tr[x]=b;
	}
	else
	{
		if(tr[x].ask(p[l])<b.ask(p[l])) insert(ls[x],l,mid,b);
		if(tr[x].ask(p[r])<b.ask(p[r])) insert(rs[x],mid+1,r,b);
	}
}
int merge(int x,int y,int l,int r)
{
	if(!x || !y) return x+y;
	int mid=(l+r)>>1;
	ls[x]=merge(ls[x],ls[y],l,mid);
	rs[x]=merge(rs[x],rs[y],mid+1,r);
	insert(x,l,r,tr[y]);
	return x;
}
int ask(int x,int l,int r,int id)
{
	if(!x) return -inf;
	int mid=(l+r)>>1,t=tr[x].ask(p[id]);
	if(l==r) return t;
	if(mid>=id) return max(t,ask(ls[x],l,mid,id));
	return max(t,ask(rs[x],mid+1,r,id));
}
void pre(int u,int fa)
{
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v,c=e[i].c;
		if(v==fa) continue;
		d[v]=d[u]+c;
		pre(v,u);
	}
}
void dfs(int u,int fa)
{
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		rt[u]=merge(rt[u],rt[v],1,n);
	}
	int id=lower_bound(p+1,p+1+n,a[u]+d[u])-p; 
	dp[u]=max(0ll,ask(rt[u],1,n,id));
	int K=b[u],B=dp[u]-d[u]*b[u];
	insert(rt[u],1,n,node(K,B));
}
signed main()
{
	//freopen("journey.in","r",stdin);
	//freopen("journey.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),c=read();
		e[++tot]=edge(v,c,f[u]),f[u]=tot;
		e[++tot]=edge(u,c,f[v]),f[v]=tot;
	}
	pre(1,0);
	for(int i=1;i<=n;i++)
		p[i]=d[i]+a[i];
	sort(p+1,p+1+n);//要排序 
	dfs(1,0);
	for(int i=1;i<=n;i++)
		printf("%lldn",dp[i]);
}
/*
dp[i]=dp[j]+(a[i]+d[i]-d[j])b[j]
那么维护 b[j]x+dp[j]-d[j]b[j]
求x=a[i]+d[i]在最大值y
*/

最后

以上就是朴实香氛为你收集整理的[unknown OJ] ZZH的旅行的全部内容，希望文章能够帮你解决[unknown OJ] ZZH的旅行所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。