NOI2014 购票

题目:

  今年夏天,NOI 在 SZ 市迎来了她 30 周岁的生日。来自全国 个城市的 OIer 们都会从各地出发,到 SZ 市参加这次盛会。
  全国的城市构成了一棵以 SZ 市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 个城市用 的整数编号。其中 SZ 市的编号为 。对于除 SZ 市之外的任意一个城市 ,我们给出了它在这棵树上的父亲城市  以及到父亲城市道路的长度
  从城市 前往 SZ 市的方法为:选择城市 的一个祖先 ,支付购票的费用,乘坐交通工具到达 。再选择城市 的一个祖先 ,支付费用并到达 。以此类推,直至到达 SZ 市。
  对于任意一个城市 ,我们会给出一个交通工具的距离限制 。对于城市 的祖先 ,只有当它们之间所有道路的总长度不超过  时,从城市 才可以通过一次购票到达城市 ,否则不能通过一次购票到达。对于每个城市 ,我们还会给出两个非负整数  作为票价参数。若城市 到城市 所有道路的总长度为 ,那么从城市 到城市 购买的票价为
  每个城市的 OIer 都希望自己到达 SZ 市时,用于购票的总资金最少。你的任务就是,告诉每个城市的 OIer 他们所花的最少资金是多少。

思路:

  
  整理一下得到:
  显然可以发现花括号中的式子是可以斜率优化的。
解法一:
  注意到切分中有一档满足 ,那就先忽略 的限制。所以能转移到 的点也就是 到根的路径上的所有点,在树上遍历时维护一个dfs栈中的元素组成的凸包,因为 不单调,所以查询要用二分实现。在树上遍历时需要回溯,所以插入时也用二分实现。这样就得到了一个 的做法。
  在加入 的限制,也就是说现在能转移的是一个区间,所以尝试线段树。在线段树上的每个结点维护当前区间内的点组成的凸包(类似归并树?),插入和回溯还是类似。查询就取每个区间的最大值的最大值。复杂度
解法二:
  还有一个链的切分档。在链上解决这个问题就可以尝试分治了,当用 中的点更新 时,对 中的点按照 排序, 中的点按照 排序,更新右区间中的 时把所有满足的点加入凸包即可。
  考虑如何搬到树上(用类似点分治的办法?),先找到重心。设 是当前树中在原树上深度最浅的点,先递归 所在的子树(类似分治中先处理左区间),把重心到 路径上的所有点构成一个凸包,用这个凸包更新其他的点。再递归其他子树。因为 不单调,所以查询得二分。复杂度
  ps:因为重心既是被更新的点,也是更新其它点的点,所以还要用重心更新一次所有的点(具体见代码)。

代码:

解法一:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define SZ(p) ((int) p.size() - 1)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ldb;
const int N = 2e5 + 5;

bool cur1;

template<class T> 
inline void rd(T &a) {
    char c;
    bool f = false;
    for(c = getchar(); !isdigit(c); c = getchar()) f |= (c == '-');
    for(a = 0; isdigit(c); c = getchar()) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
}

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
struct Edge {int to; ll w;};
Link<N, N, Edge> G;

int f[N], n, t;
ll s[N], p[N], q[N], lm[N];
ll val[N], dis[N];

struct Point {
    ll x, y;
};
bool cmp(Point a, Point b, Point c) {
    return (ldb) (c.y - b.y) * (b.x - a.x) <= (ldb) (b.y - a.y) * (c.x - b.x);
}
bool cmp(Point a, Point b, ll t) {
    return (b.y - a.y) < (ldb) (b.x - a.x) * t;
}
struct Convex {
    vector<Point> p, stk;
    vector<int> top;
    Convex() {top.push_back(-1);}
    void add(Point o) {
        int l = 1, r = top.back(), m, t = r + 1;
        while(l <= r) {
            m = (l + r) >> 1;
            if(cmp(p[m - 1], p[m], o)) t = m, r = m - 1;
            else l = m + 1;
        }
        if(p.size() <= t) p.push_back((Point) {0, 0});
        stk.push_back(p[t]);
        top.push_back(t);
        p[t] = o;
    }
    ll query(ll t) {
        int l = 1, r = top.back(), m, x = 0;
        while(l <= r) {
            m = (l + r) >> 1;
            if(cmp(p[m - 1], p[m], t)) x = m, l = m + 1;
            else r = m - 1;
        }
        return p[x].y - t * p[x].x;
    }
    void undo() {
        int t = top.back();
        Point o = stk.back();
        top.pop_back(); stk.pop_back();
        p[t] = o;
    }
} seg[N << 2];

#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((L + R) >> 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
void add(int w, Point x, int o, int L, int R) {
    seg[o].add(x);
    if(L == R) return;
    if(w <= mid) add(w, x, lson);
    else add(w, x, rson);
}
void undo(int w, int o, int L, int R) {
    seg[o].undo();
    if(L == R) return;
    if(w <= mid) undo(w, lson);
    else undo(w, rson);
}
ll query(int l, int r, int t, int o, int L, int R) {
    if(l == L && r == R) {
        ll x = seg[o].query(p[t]);
        return x + dis[t] * p[t] + q[t];
    }
    if(r <= mid) return query(l, r, t, lson);
    else if(l > mid) return query(l, r, t, rson);
    else return min(query(l, mid, t, lson), query(mid + 1, r, t, rson));
}

int stk[N];
void dfs(int o, int top) {
    if(o != 1) {
        int l = 1, r = top, m, t;
        while(l <= r) {
            m = (l + r) >> 1;
            if(dis[o] - dis[stk[m]] <= lm[o])
                r = m - 1, t = m;
            else
                l = m + 1;
        }
        val[o] = query(t, top, o, 1, 1, n);
    }
    stk[++top] = o;
    add(top, (Point) {dis[o], val[o]}, 1, 1, n);
    erep(k, G, o) {
        Edge e = G[k];
        dis[e.to] = dis[o] + e.w;
        dfs(e.to, top);
    }
    undo(top, 1, 1, n);
}

bool cur2;

int main() {
    // printf("%lf\n", (&cur2 - &cur1) / 1024.0 / 1024);
    File(ticket);
    rd(n); rd(t);
    rep(i, 2, n) {
        rd(f[i]); rd(s[i]); rd(p[i]); rd(q[i]); rd(lm[i]);
        G.add(f[i], (Edge) {i, s[i]});
    }
    dfs(1, 0);
    rep(i, 2, n) printf("%lld\n", val[i]);
    return 0;
}

解法二:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ldb;
const int N = 2e5 + 5;

bool cur1;

template<class T> 
inline void rd(T &a) {
    char c;
    bool f = false;
    for(c = getchar(); !isdigit(c); c = getchar()) f |= (c == '-');
    for(a = 0; isdigit(c); c = getchar()) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
}

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
struct Edge {int to; ll w;};
Link<N, N << 1, Edge> G;

ll dis[N], lm[N], val[N], p[N], q[N];
int fa[N];
void dfs_dis(int o, int f) {
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f) continue;
        dis[v] = dis[o] + G[k].w;
        dfs_dis(v, o);
    }
}

int size[N];
bool mark[N];
void dfs_size(int o, int f, int tot, int &id, int &mx) {
    size[o] = 1;
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f || mark[v]) continue;
        dfs_size(v, o, tot, id, mx);
        size[o] += size[v];
    }
    if(tomin(mx, max(tot - size[o], size[o]))) id = o;
}
int getRt(int o, int tot) {
    dfs_size(o, 0, tot, o, tot);
    return o;
}

struct Point {
    ll x, y;
};
bool cmp(Point a, Point b, Point c) {
    return (ldb) (c.y - b.y) * (b.x - a.x) <= (ldb) (b.y - a.y) * (c.x - b.x);
}
bool cmp(Point a, Point b, ll t) {
    return (b.y - a.y) < (ldb) (b.x - a.x) * t;
}
struct Convex {
    Point p[N];
    int top;
    void clear() {top = 0;}
    void add(Point o) {
        while(top > 1 && cmp(p[top - 1], p[top], o)) top--;
        p[++top] = o;
    }
    bool empty() {return top == 0;}
    ll query(ll t) {
        int l = 2, r = top, m, x = 1;
        while(l <= r) {
            m = (l + r) >> 1;
            if(cmp(p[m - 1], p[m], t)) x = m, l = m + 1;
            else r = m - 1;
        }
        return p[x].y - t * p[x].x;
    }
} con;

int grd[N], tot_g, vec[N], tot_v;
void dfs_vec(int o, int f) {
    vec[++tot_v] = o;
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f || mark[v]) continue;
        dfs_vec(v, o);
    }
}
bool cmp_vec(int x, int y) {
    return dis[x] - lm[x] > dis[y] - lm[y];
}

void calc() {
    con.clear();
    sort(vec + 1, vec + 1 + tot_v, cmp_vec);
    int t = 1;
    rep(i, 1, tot_v) {
        int o = vec[i];
        for(; t <= tot_g && dis[grd[t]] >= dis[o] - lm[o]; t++)
            con.add((Point) {-dis[grd[t]], val[grd[t]]});
        if(!con.empty()) 
            tomin(val[o], con.query(-p[o]) + dis[o] * p[o] + q[o]);
    }
}
void dfs(int o, int rt, int tot) {
    mark[o = getRt(o, tot)] = true;
    if(!mark[fa[o]]) 
        dfs(fa[o], rt, size[fa[o]] < size[o] ? size[fa[o]] : tot - size[o]);
    tot_g = 0;
    for(int p = fa[o]; p != fa[rt]; p = fa[p]) 
        grd[++tot_g] = p;
    vec[tot_v = 1] = o;
    erep(k, G, o) 
        if(!mark[G[k].to] && G[k].to != fa[o])
            dfs_vec(G[k].to, o);
    calc();
    rep(i, 1, tot_v) {
        int v = vec[i];
        if(o == v) continue;
        if(dis[v] - dis[o] <= lm[v]) 
            tomin(val[v], val[o] + (dis[v] - dis[o]) * p[v] + q[v]);
    }
    erep(k, G, o) {
        int v = G[k].to;
        if(mark[v] || v == fa[o]) continue;
        dfs(v, v, size[v] < size[o] ? size[v] : tot - size[o]);
    }
}

bool cur2;

int main() {
    // printf("%lf\n", (&cur2 - &cur1) / 1024.0 / 1024);
    File(ticket);
    int n, t;
    rd(n); rd(t);
    rep(i, 2, n) {
        int s;
        rd(fa[i]); rd(s); rd(p[i]); rd(q[i]); rd(lm[i]);
        G.add(fa[i], (Edge) {i, s});
        G.add(i, (Edge) {fa[i], s});
    }
    dfs_dis(1, 0);
    rep(i, 2, n) val[i] = 1e18;
    dfs(1, 1, n);
    rep(i, 2, n) printf("%lld\n", val[i]);
    return 0;
}