ZZH的旅行题目思路代码

51 阅读 0 评论 34 点赞

我是靠谱客的博主背后中心，最近开发中收集的这篇文章主要介绍ZZH的旅行题目思路代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

传送门 to usOJ

题目背景
机房里有一个姓周的妹儿，由于喜欢 “有问题，上 $z h$ ” ，大家都叫她 $z z h$ 。

题目描述
$z z h$ 喜欢当女未女未，所以对于一棵树，她不喜欢深度减小（成为别人的祖先），她只想变成叶子节点。

具体而言，她一开始站在 $x$ 号节点，然后一直往子树内走，有选择性地 找一些地方歇脚。毫无疑问 $x$ 是她的一个休息站。在两个休息站 $x \to y$ 之间，我们认为 $z z h$ 的快乐程度为 $a_x-dis_{x,y})b_y$ ，这里 $a, b$ 是每个休息站固有的属性（~~是热水供应和方便面的包数~~）。

现在你能对于每个 $x$ 求出最大快乐程度吗？提示一下，这一定是个正数，大不了不移动。

数据范围与提示
$10^6$ （但是并非线性解法）且 $max(a_i,b_i)le 10^9$ 。

数据保证根节点 $1$ 到每个点的距离不超过 $10^9$ ，保证答案不超过 $10^{17}$ 。

思路

显然 $d p$ 的斜率优化板题。平衡树可以做到 $O (n lo g n)$ ，详见 $s p l a y$ 启发式合并。

然而今天开了眼界，斜率优化也可以看成很多条直线，然后对于一个 $x$ 求最大的 $y$ 。然后成为了 李超树 板题。而且复杂度很正确，因为这里加入的是直线而非线段。线段树合并当然也是一个 $lo g$ 。

所以复杂度都是 $O (n lo g n)$ ，但是李超树明显好写很多——我现在还没调出平衡树版本。

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

struct Line{
	int k; int_ b; // y = kx + b
	Line(){ k = b = 0; }
	Line(int K,int_ B):k(K),b(B){}
	int_ operator()(const int &x) const {
		return 1ll*k*x+b;
	}
};

const int MaxN = 1000005; // 1e6

const int MaxR = 2e9; // max(dep + a)
int son[MaxN*10][2], cntNode;
int rt[MaxN]; // 每个点对应的子树的线段树的根
Line v[MaxN*10]; // 每个点上面存一条线
void modify(Line t,int &o,int l=0,int r=MaxR){
	if(!o) o = ++ cntNode; // 开新点
	if(t(l) > v[o](l)) swap(v[o],t);
	if(t(r) <= v[o](r)) return ; // 完全在下
	int mid = (0ll+l+r)>>1; // 中间点
	if(t(mid) <= v[o](mid)) // 右边突出
		modify(t,son[o][1],mid+1,r);
	else{ // 早就超过了自己
		swap(v[o],t); // 自己用长的
		modify(t,son[o][0],l,mid);
	}
}
/** @param o_ 将要并入的线段树 */
void mergeTree(int &o,int o_,int l=0,int r=MaxR){
	if(!o || !o_) return void(o += o_);
	int mid = (0ll+l+r)>>1;
	mergeTree(son[o][0],son[o_][0],l,mid);
	mergeTree(son[o][1],son[o_][1],mid+1,r);
	modify(v[o_],o,l,r); // 将直线合并起来
}
int_ query(int qid,int o,int l=0,int r=MaxR){
	if(!o) return 0; // 根本没得线段
	int_ res = v[o](qid); // 一路上均可取值
	if(l == r) return res;
	int mid = (0ll+l+r)>>1;
	if(qid <= (l+r)>>1)
		res = max(res,query(qid,son[o][0],l,mid);
	else res = max(res,query(qid,son[o][1],mid+1,r));
	return res; // 一路往下查
}

struct Edge{
	int to, nxt, val;
	Edge(){ }
	Edge(int T,int N,int V){
		to = T, nxt = N, val = V;
	}
};
Edge e[MaxN<<1];
int head[MaxN], cntEdge;
void addEdge(int a,int b,int c){
	e[cntEdge] = Edge(b,head[a],c);
	head[a] = cntEdge ++;
}

int a[MaxN], b[MaxN], dep[MaxN];
int_ dp[MaxN];
void dfs(int x,int pre){
	for(int i=head[x]; ~i; i=e[i].nxt)
		if(e[i].to != pre){
			dep[e[i].to] = dep[x]+e[i].val;
			dfs(e[i].to,x);
			mergeTree(rt[x],rt[e[i].to]);
		}
	dp[x] = query(dep[x]+a[x],rt[x]);
	modify(Line(b[x],dp[x]-1ll*b[x]*dep[x]),rt[x]);
}

int main(){
	int n = readint();
	for(int i=1; i<=n; ++i){
		a[i] = readint(), b[i] = readint();
		head[i] = -1;
	}
	for(int i=1,x,y,w; i<n; ++i){
		x = readint(), y = readint();
		addEdge(x,y,w = readint());
		addEdge(y,x,w); // 不知父子关系
	}
	dfs(1,-1);
	for(int i=1; i<=n; ++i)
		printf("%lldn",dp[i]);
	return 0;
}

/*

val[j] = dp[j] - b_j * dep[b]

dp[i] = val[j] + b_j * (dep[a] + a_i)

*/