记录编号	451932	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]购票	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	4.771 s
提交时间	2017-09-18 17:23:04	内存使用	20.32 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
#define ld long double
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x7f7f7f7f7f7f7f7f;
using namespace std;

template<typename T>
//Positive Integers Only
inline void read(T &x) {
	char ch; while((ch = getchar()), (ch < '0' || ch > '9'));
	x = ch - '0'; while((ch = getchar()), (ch >= '0' && ch <= '9')) x = x * 10 + (ch - '0');
}

const int MAXN = 200010;

int N, T;
int fa[MAXN]; ll falen[MAXN], P[MAXN], Q[MAXN], L[MAXN], dis[MAXN];

ll dp[MAXN];
struct pt { //x: dis, y: dp
	ll x, y;
	inline pt operator-(pt rhs) { return (pt) { x - rhs.x, y - rhs.y }; }
};
inline ll dec(int i, pt p) {
	if(dis[i] == p.x) return INFLL; //not update self by self
	return p.y + P[i] * (dis[i] - p.x) + Q[i];
}
inline pt point(int x) {
	return {dis[x], dp[x]};
}
namespace CH {
	inline ld cross(pt v, pt w) { return (ld)v.x * w.y - (ld)w.x * v.y; }
	int n; pt CH[MAXN];
	inline void ins(int idx) {
		pt p = point(idx);
		//CH Del From Head!!!
		while(n >= 2 && cross(CH[n - 1] - CH[n - 2], p - CH[n - 2]) >= 0) n--;
		CH[n++] = p;
	}
}

int head[MAXN], next[MAXN], tail[MAXN], id = 1;
ll len[MAXN];
inline void link(int u, int v, ll d) {
	next[id] = head[u]; tail[id] = v; len[id] = d; head[u] = id++;
}

struct node {
	int u; ll dis;
	inline bool operator<(node rhs) const {
		return dis > rhs.dis;
	}
} V[MAXN]; int Nv;

bool vis[MAXN];
int totsz, cenid, censz, size[MAXN];
void dfssz(int u) {
	int i, v, maxsz = 0;
	size[u] = 1;
	for(i = head[u]; i; i = next[i]) {
		v = tail[i];
		if(!vis[v]) dfssz(v), maxsz = max(maxsz, size[v]), size[u] += size[v];
	}
	maxsz = max(maxsz, totsz - size[u]);
	if(maxsz < censz) censz = maxsz, cenid = u;
}

void dfssub(int u) {
	int i, v;
	for(i = head[u]; i; i = next[i]) {
		v = tail[i];
		if(!vis[v]) V[Nv++] = {v, dis[v] - L[v]}, dfssub(v);
	}
}

void dfs(int u, int tot) {
	//find centroid
	totsz = tot; censz = INF;
	dfssz(u);
	//find fa
	int c = cenid;
	vis[c] = 1;

	int i, v;
	if(c != u) {
		dfs(u, tot - size[c]);
		v = c;
		do {
			v = fa[v];
			if(dis[c] - dis[v] > L[c]) break;
			dp[c] = min(dp[c], dec(c, point(v)));
		} while(v != u);
	}

	//Sort Sub-nodes
	Nv = 0; dfssub(c);
	sort(V, V + Nv);
	//Update sub-nodes
	int f = c;
	CH::n = 0;
	//printf("U = %d\n", c);
	for(i = 0; i < Nv; i++) {
		while(f && dis[f] >= V[i].dis) {
			CH::ins(f);
			f = f == u ? 0 : fa[f];
		}
		int x, L = 0, R = CH::n - 1, M1, M2;
		while(R - L > 3) {
			M1 = L + (R - L) / 3;
			M2 = R - (R - L) / 3;
			if(dec(V[i].u, CH::CH[M1]) < dec(V[i].u, CH::CH[M2])) R = M2; else L = M1;
		}
		for(x = L; x <= R; x++) dp[V[i].u] = min(dp[V[i].u], dec(V[i].u, CH::CH[x]));
	}
	//for(i = 0; i < CH::n; i++) printf("[%lld %lld]\n", CH::CH[i].x, CH::CH[i].y);
	//Dfs Sub-nodes
	for(i = head[c]; i; i = next[i]) {
		v = tail[i];
		if(!vis[v]) dfs(v, size[v]);
	}
}

void dfsdis(int u, ll d) {
	int i, v;
	dis[u] = d;
	for(i = head[u]; i; i = next[i]) v = tail[i], dfsdis(v, d + len[i]);
}

int main() {
	int size = 128 << 20;
    char *p = (char*)malloc(size) + size;  
    __asm__("movl %0, %%esp\n" :: "r"(p));

	freopen("ticket.in", "rt", stdin);
	freopen("ticket.out", "wt", stdout);

	int i;
	read(N), read(T);
	for(i = 2; i <= N; i++) {
		read(fa[i]), read(falen[i]), read(P[i]), read(Q[i]), read(L[i]);
		link(fa[i], i, falen[i]);
	}
	memset(dp, 0x7f, sizeof(dp)); dp[1] = 0;
	dfsdis(1, 0);
	dfs(1, N);

	for(i = 2; i <= N; i++) printf("%lld\n", dp[i]);
	return 0;
}