记录编号	255236	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]购票	最终得分	100
用户昵称	thomount	是否通过	通过
代码语言	C++	运行时间	5.999 s
提交时间	2016-04-27 10:22:22	内存使用	44.54 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	long long ans = 0;
	while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
	return ans;
}
const int N = 200010;
const long long ml = 1ll << 60;
const double eps = 1e-6;
struct edge {
	int x, y, next;
	long long z;
	edge(int x = 0, int y = 0, long long z = 0, int next = -1): x(x), y(y), z(z), next(next) {}
} e[N];
int h[N], ett = 0;
inline void match(int x, int y, long long z) {e[ett] = edge(x, y, z, h[x]); h[x] = ett++;}
struct info {
	int x;
	long long y, z;
} op[N];
long long ans[N], dist[N];
int fa[N], dp[N], size[N], son[N], par[N], id[N], ttt = 0;
void dfs1(int x) {
	dp[x] = dp[fa[x]] + 1;
	size[x] = 1; son[x] = 0;
	int p = h[x];
	while (p != -1) {
		dist[e[p].y] = dist[x] + e[p].z;
		dfs1(e[p].y);
		size[x] += size[e[p].y];
		if (!son[x] || size[e[p].y] > size[son[x]]) son[x] = e[p].y;
		p = e[p].next;
	}
}
void dfs2(int x, int P) {
	par[x] = P;
	id[x] = ++ttt;
	if (son[x]) dfs2(son[x], P);
	int p = h[x];
	while (p != -1) {
		if (e[p].y != son[x]) dfs2(e[p].y, e[p].y);
		p = e[p].next;
	}
}
struct point {
	long long x, y;
	point(long long x = 0, long long y = 0): x(x), y(y) {}
} p[N];
inline point operator - (point a, point b) {return point(a.x-b.x, a.y-b.y);}
inline int operator * (point a, point b) {return (((double)a.x*b.y - (double)a.y*b.x) > -eps) ? 1: -1;}
inline bool operator < (point a, point b) {return (a.x == b.x)? (a.y < b.y): (a.x < b.x);}
inline bool cmp(int x, int y) {return p[x] < p[y];}
struct node {
	int l, r, st, en;
	node * ls, * rs;
	node(int l = 0, int r = 0): l(l), r(r), st(0), en(0), ls(0), rs(0) {}
} d[N*2];
typedef node * link;
int ptt = 0;
link head;
link build(int l, int r) {
	d[++ptt] = node(l, r);
	link p = &d[ptt];
	if (l < r) {
		int mid = (l + r) >> 1;
		p->ls = build(l, mid);
		p->rs = build(mid+1, r);
	}
	return p;
}
int q[N*20], temp[N], top = 0;
void cal(link P) {
	int n = 0;
	for (int i = P->l; i <= P->r; i++) temp[++n] = i;
	sort(temp+1, temp+n+1, cmp);
	int up = top+1;
	for (int i = 1; i <= n; i++) {
		while (top > up && (p[temp[i]] - p[q[top]]) * (p[q[top]] - p[q[top-1]]) >= 0) top--;
		q[++top] = temp[i];
	}
	P->st = up, P->en = top;
}

long long get(int l, int r, long long k) {
	if (l == r) return p[q[r]].y - p[q[r]].x * k;	//区间为1的特判
	point temp = point(1, k);
	if ((p[q[r]] - p[q[r-1]]) * temp >= 0) return p[q[r]].y - p[q[r]].x * k;
	if (temp * (p[q[l+1]] - p[q[l]]) >= 0) return p[q[l]].y - p[q[l]].x * k;	//边界特判
	l++, r--;
	while (l < r) {
		int mid = (l + r) >> 1;
		int k1 = temp * (p[q[mid+1]] - p[q[mid]]), k2 = (p[q[mid]] - p[q[mid-1]]) * temp;
		if (k1 >= 0 && k2 >= 0) {l = r = mid; break;}
		if (k1 < 0) l = mid+1; else r = mid-1;
	}
	return p[q[l]].y - p[q[l]].x * k;
}
long long check(link p, int l, int r, long long k) {
	if (l > r) return ml;
	if (l <= p->l && p->r <= r) {
		if (!p->st) cal(p);
		return get(p->st, p->en, k);
	}
	int mid = (p->l + p->r) >> 1;
	long long ans = ml;
	if (l <= mid) ans = min(ans, check(p->ls, l, r, k));
	if (mid < r) ans = min(ans, check(p->rs, l, r, k));
	return ans;
}
int find(int l, int r, long long k) {
	if (k < p[l].x) return l;
	if (k > p[r].x) return r+1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (k <= p[mid].x) r = mid; else l = mid+1;
	}
	return l;
}
long long update(int x) {
	int y = fa[x], fy = par[y];
	long long ans = ml;
	while (y && dist[x] - dist[y] <= op[x].z) {
		int st;		//本段起点
		if (dist[x] - dist[fy] <= op[x].z) st = id[fy];	else st = find(id[fy], id[y], dist[x] - op[x].z);
		ans = min(ans, check(head, st, id[y], op[x].x));
		y = fa[fy]; fy = par[y];
	}
	return ans + dist[x] * op[x].x + op[x].y;
}

int main() {
	freopen("ticket.in", "r", stdin);
	freopen("ticket.out", "w", stdout);
	int n = read(), T = read();
	memset(h, -1, sizeof(h));
	for (int i = 2; i <= n; i++) {
		int fx = read();
		long long sx = read();
		match(fx, i, sx);
		fa[i] = fx;
		op[i].x = read(), op[i].y = read(), op[i].z = read();
	}
	dist[1] = 0; dp[0] = 0;
	dfs1(1);	// son size dist dp
	dfs2(1, 1);	// par id 
	
	head = build(1, n);
	ans[1] = 0; p[1] = point(0, 0);
	for (int i = 2; i <= n; i++) {
		printf("%lld\n", ans[i] = update(i));
		p[id[i]] = point(dist[i], ans[i]);
	}
	return 0;
}