题解 P2305 【[NOI2014]购票 】
行吟啸九州
·
·
题解
这个题体现了OI题的很多题的出题思路，一个问题可以在序列轻松解决，就把它拿到树上来出题。
这题所有数据点都需要开long long，要不然读入就跪了。
算法一：对于1-3个点，我们可以直接暴力dp的去做，求每个点的dp值时可以暴力枚举他的祖先去更新，复杂度O(n ^ 2)，期望得分30分，适合于考试的时候实在没有时间的时候去写，或者用作对拍的暴力。
算法二：不难发现，这是一个1D/1D的dp,观察式子发现可以斜率优化。
$t = 2$时, 这个$l[i]$的限制，就感觉有点像单调队列优化和斜率优化的结合体，这个可以用离散化加李超线段树或者线段树维护凸包解决，复杂度O($n\log ^ 2n$)。
算法二结合算法一期望得分50分。
算法三：如果只想到了李超线段树，序列上问题虽然可以解决，但是拿到树上，可能就需要可持久化了。我个人并不知道如何可持久化的李超线段树，所以还是使用线段树维护凸包解决。
对于$t = 1$的点，每个点只会更新他子树内的点，对树进行树剖，处理完某个点后，对它子树内的点维护的凸包里插入这个点即可。
复杂度O($n\log n$)，结合上述算法期望得分80分。
算法四：我们之前的思路，大多数是用祖先去更新后代，不过因为有了$l[i]$这个点，每个点对之后的点的贡献区间就很难加以计算了。
这里有一个树上很常见的技巧，一个点向下走L深度的链有很多，向上走L深度的链只有一个。所以我们可以让一个点去找祖先要贡献代替祖先去更新后代。用树剖+线段树维护凸包即可实现。复杂度O($n\log ^3n$)，期望得分100分。
算法四这个方法在2014年估计是过不去的，因为那个时候的机器跑得很慢，不过在今天只要你常数正常，就能通过。
十分好写，没有任何细节，找祖先更新的时候需要倍增一下估计也不是什么难点。
顺道说一下，有一篇题解认为，一个线段树区间如果维护不是一条链就不能插入点。这个时候不插入肯定没有问题，不过你插入了，也没有问题，因为查询的时候，一定不会查询这个区间。暴力插入，能更好写一些，可能常数因此略大一些。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define maxt 800005
#define int long long
#define inf 2003518617518617ll
#define Fol(i, j, n) for(register int i = j ; i >= n ; --i)
#define For(i, j, n) for(register int i = j ; i <= n ; ++i)
int n, t, tot, l[maxn], p[maxn], q[maxn], w[maxn], dp[maxn];
int fa[maxn], dep[maxn], dfn[maxn], siz[maxn], top[maxn], mson[maxn], up[maxn][22];
vector<int>E[maxn];
struct Point{
int x, y;
Point(int xx = 0, int yy = 0){ x = xx, y = yy; }
};
vector<Point>c[maxt];
//线段树维护凸包
#define ls x << 1
#define rs x << 1 | 1
#define mid (l + r >> 1)
inline double K(Point a, Point b){ return (double)(b.y - a.y) / (b.x - a.x); }
inline int Query(int x, int ll, int rr, int k){
int l = 0, r = (int)c[x].size() - 2, ans = c[x][r + 1].x * k + c[x][r + 1].y;
while(l <= r){
ans = min(ans, c[x][mid].x * k + c[x][mid].y);
if(K(c[x][mid], c[x][mid + 1]) <= k) l = mid + 1;
else r = mid - 1;
}
return ans;
}
inline int query(int x, int l, int r, int ql, int qr, int k){
if(ql <= l && r <= qr) return Query(x, l, r, k);
int sum = inf;
if(ql <= mid) sum = min(sum, query(ls, l, mid, ql, qr, k));
if(qr > mid) sum = min(sum, query(rs, mid + 1, r, ql, qr, k));
return sum;
}
inline void add(int x, int l, int r, Point y){
for( ; c[x].size() > 1 ; c[x].pop_back()){
int n = (int)c[x].size() - 1;
Point a = c[x][n], b = c[x][n - 1];
if(K(b, y) > K(b, a)) break;
}
c[x].push_back(y);
}
inline void insert(int x, int l, int r, int pos, Point y){
add(x, l, r, y);
if(l == r) return ;
pos <= mid ? insert(ls, l, mid, pos, y) : insert(rs, mid + 1, r, pos, y);
}
//树剖
inline void dfs(int x){
siz[x] = 1, dep[x] = dep[fa[x]] + w[x], up[x][0] = fa[x];
For(i, 1, 20) up[x][i] = up[up[x][i - 1]][i - 1];
for(auto i : E[x]){
if(siz[i]) continue;
dfs(i), siz[x] += siz[i];
if(siz[i] > siz[mson[x]]) mson[x] = i;
}
}
inline void dfs(int x, int tp){
top[x] = tp, dfn[x] = ++tot;
if(mson[x]) dfs(mson[x], tp);
for(auto i : E[x]) if(!dfn[i]) dfs(i, i);
}
// dp
inline int query(int x, int L){
Fol(i, 20, 0) if(dep[up[x][i]] >= L) x = up[x][i];
return x;
}
inline int Query(int x, int y, int k){
int ans = inf;
while(top[x] ^ top[y]) ans = min(ans, query(1, 1, n, dfn[top[x]], dfn[x], k)), x = fa[top[x]];
return min(ans, query(1, 1, n, dfn[y], dfn[x], k));
}
inline void solve(int x){
if(x ^ 1) dp[x] = Query(fa[x], query(x, dep[x] - l[x]), -p[x]) + dep[x] * p[x] + q[x];
insert(1, 1, n, dfn[x], Point(dep[x], dp[x]));
for(auto i : E[x]) solve(i);
}
//主函数
signed main(){
scanf("%lld %lld", &n, &t);
For(i, 2, n) scanf("%lld %lld %lld %lld %lld", &fa[i], &w[i], &p[i], &q[i], &l[i]), E[fa[i]].push_back(i);
dfs(1), dfs(1, 1), dep[0] = -inf, solve(1);
For(i, 2, n) printf("%lld\n", dp[i]);
return 0;
}
```