首页 > 代码库 > cogs2652 秘术「天文密葬法」

cogs2652 秘术「天文密葬法」

2024-10-17 08:19:39   214人阅读

传送门：http://cogs.pro/cogs/problem/problem.php?pid=2652

【题解】

学习了一发长链剖分，感觉十分兹磁

广告：长链剖分 - fjzzq2002

那么我再说一遍吧，以本题为例。

题目大意：给一棵树，每个点有点权$A_i$和$B_i$，找一条长度为$m$的路径，使得$\frac{\sum_{j~in~route}A_j}{\sum_{j~in~route}B_j}$最小。

显然分数规划，二分答案$p$，那么将每个点的点权变成$A_j - p*B_j$，显然最后只要判是否存在一条长度为$m$的路径使得总和小于等于0即可。

首先点分治是可行的，总复杂度为$O(nlog^2n)$。

考虑一种复杂度为$O(nlogn)$的做法：长链剖分。

本文剩下部分不介绍复杂度，要分析复杂度可以看上面链接中的口胡，或者Google下

考虑一种dp方法：$f_{x,i}$表示$x$节点的子树中，往下走$i$步的最小值。

很明显可以使用子树合并的技巧来算答案、更新f数组。

但是这样太慢了，复杂度为$O(n^2)$，还不如写点分治！

但是，考虑一开始f数组的初始值为最长链所在儿子的值，接着依次暴力合并其他儿子，这样复杂度就对了！

我们还需要考虑的是：

①空间问题

②点权问题

先来考虑空间，我们给按类似轻重链剖分（这里用最长链替换重儿子）的方式，给点编号$pos_x$，我们只开一个$O(n)$的dp数组$dp$来完成操作。

那么令$f_{x,0} = dp_{pos_x}$。有人问，其他的值呢？

考虑$x$往下的最长链的值，一定存储在$dp_{pos_x+1}$开始的连续位置，那么他们对于$x$，恰好是需要多走一步，那么实际上他们现在的位置就是对的了，就可以当做是$f_{x,1}$……的了！！！

这样就非常妙了，我们用$O(n)$的空间，实现了$O(n^2)$的动态规划。

考虑加入一个点还需要点权，那么如果暴力把长链上的所有dp值肯定不现实，复杂度肯定是错的。

考虑每个点引入$tag_x$，表示这个点全局加了多少，类似于noip2016 蚯蚓的全局增加量。只不过这里的全局指的是子树。

然后能做啦！

代码还很好写，比垃圾点分治好多啦！

技术分享 
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 3e4 + 10, M = 6e4 + 10;
const int mod = 1e9+7;

int n, m, A[N * 7], B[N * 7], head[N], nxt[M], to[M], tot = 0; 
inline void add(int u, int v) {
    ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
}
inline void adde(int u, int v) {
    add(u, v), add(v, u);
}

int dep[N], mxd[N], son[N], sz[N]; 
inline void pre_dfs(int x, int fa = 0) {
    dep[x] = dep[fa] + 1;
    mxd[x] = dep[x]; son[x] = 0;
    for (int i=head[x]; i; i=nxt[i]) {
        if(to[i] == fa) continue;
        pre_dfs(to[i], x);
        if(mxd[to[i]] > mxd[x]) mxd[x] = mxd[to[i]], son[x] = to[i];        
    }
    sz[x] = mxd[x] - dep[x]; 
}

int pos[N], idx; 
inline void pre_pos(int x, int fa = 0) {
    pos[x] = ++idx;
    if(son[x]) pre_pos(son[x], x);
    for (int i=head[x]; i; i=nxt[i]) 
        if(to[i] != fa && to[i] != son[x]) pre_pos(to[i], x);        
}

double mid_check, ans;
double dp[N], tag[N]; 
inline void solve(int x, int fa = 0) {
    double *f = &dp[pos[x]], C = (double)A[x] - mid_check * B[x]; 
    if(son[x] == 0) {    //leaf
        f[0] = C; tag[x] = 0; 
        if(m == 0) ans = min(ans, f[0]); 
        return ;
    }
    solve(son[x], x); f[0] = -tag[son[x]];
    tag[x] = tag[son[x]] + C; 
    for (int i=head[x], y; i; i=nxt[i]) {
        if(to[i] == fa || to[i] == son[x]) continue;
        solve(y = to[i], x);
        double *g = &dp[pos[y]];
        for (int j=0; j<=sz[y] && j<m; ++j)
            if(m-1-j <= sz[x]) ans = min(ans, f[m-1-j] + tag[x] + g[j] + tag[y]); 
         for (int j=0; j<=sz[y]; ++j) f[j+1] = min(f[j+1], g[j] + tag[y] + C - tag[x]); 
    }
    if(m <= sz[x]) ans = min(ans, f[m] + tag[x]); 
}


inline bool chk(double x) {
     ans = 1e18; mid_check = x;
     solve(1); 
    return ans <= 0; 
}

int main() {
    freopen("cdcq_b.in", "r", stdin);
    freopen("cdcq_b.out", "w", stdout); 
    cin >> n >> m; 
    for (int i=1; i<=n; ++i) scanf("%d", A+i);
    for (int i=1; i<=n; ++i) scanf("%d", B+i);
    if(m == -1) {
        double ans = 1e18;
        for (int i=1; i<=n; ++i) ans = min(ans, (double)A[i]/B[i]);
        printf("%.2lf\n", ans);
        return 0;
    }
    for (int i=1, u, v; i<n; ++i) {
        scanf("%d%d", &u, &v);
        adde(u, v);
    }
    --m;
    pre_dfs(1); 
    pre_pos(1); 
    double l = 0, r = 1e11, mid;
    while(r-l > 1e-4) {
        mid = (l+r)/2.0; 
        if(chk(mid)) r = mid;
        else l = mid;
    }
    if(l > 5e10) puts("-1");
    else printf("%.2lf\n", l); 
    return 0;
}
View Code

 

cogs2652 秘术「天文密葬法」


联系
我们