解题报告
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809
解题报告
一句话题解:树上CDQ分治
先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$
我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = N << 1; const LL INF = 6e18; int n, head[N], nxt[M], to[M], fa[N]; LL q[N], p[N], len[N], dep[N], f[N]; struct Point{ LL x, y, id, range; inline Point() { } inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) { } inline bool operator < (const Point &P) const { return x > P.x || (x == P.x && y > P.y); } inline Point operator - (const Point &P) { return Point(x - P.x, y - P.y, 0, 0); } inline double operator * (const Point &P) { return (double)x * P.y - (double)y * P.x; } inline double slope(const Point &P) { return (double)(y - P.y) / (x - P.x); } static bool update(const Point &P1, const Point &P2) { return P1.range > P2.range; } }; inline LL read() { char c = getchar(); LL ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } class DivideAndConquer{ int sz[N], vis[N]; public: inline void solve(int w, int universe) { int top = w; vis[w = FindRoot(w, universe)] = 1; if (fa[w] && !vis[fa[w]]) { solve(top, universe - sz[w]); } vector<Point> cvx; for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) { cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw])); } vector<Point> que; que.push_back(Point(dep[w], 0, w, dep[w] - len[w])); for (int i = head[w]; i; i = nxt[i]) { if (dep[to[i]] > dep[w] && !vis[to[i]]) { DFS(to[i], w, que); } } sort(que.begin(), que.end(), Point::update); sort(cvx.begin(), cvx.end()); for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) { for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) { for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot); cvx[tot++] = cvx[j]; } int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id; while (l <= r) { mid = l + r >> 1; if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) { ret = mid; r = mid - 1; } else { l = mid + 1; } } if (ret >= 0) { f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]); } } for (int i = 0, j; i < (int)que.size(); i++) { if (j = que[i].id, que[i].range <= dep[w]) { f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]); } } que.clear(); cvx.clear(); for (int i = head[w]; i; i = nxt[i]) { if (dep[to[i]] > dep[w] && !vis[to[i]]) { solve(to[i], sz[to[i]]); } } } private: inline int FindRoot(int w, int universe) { int ret = 0, ans; FindRoot(w, w, universe, ret, ans); return ret; } inline void FindRoot(int w, int f, int universe, int &ret, int &ans) { int mx = 1; sz[w] = 1; for (int i = head[w]; i; i = nxt[i]) { if (!vis[to[i]] && to[i] != f) { FindRoot(to[i], w, universe, ret, ans); sz[w] += sz[to[i]]; mx = max(mx, sz[to[i]]); } } mx = max(mx, universe - sz[w]); if (!ret || mx < ans) { ans = mx; ret = w; } } inline void DFS(int w, int f, vector<Point> &ret) { ret.push_back(Point(dep[w], 0, w, dep[w] - len[w])); for (int i = head[w]; i; i = nxt[i]) { if (!vis[to[i]] && to[i] != f) { DFS(to[i], w, ret); } } } }DAC; int main() { n = read(); read(); for (int i = 2; i <= n; i++) { fa[i] = read(); LL c = read(); AddEdge(fa[i], i); p[i] = read(); q[i] = read(); len[i] = read(); dep[i] = dep[fa[i]] + c; } fill(f, f + N, INF); f[1] = 0; dep[0] = -1; DAC.solve(1, n); for (int i = 2; i <= n; i++) { printf("%lld\n", f[i]); } return 0; }