首页 > 其他分享 >【题解】P4292 [WC2010]重建计划

【题解】P4292 [WC2010]重建计划

时间:2023-01-14 13:56:29浏览次数:66  
标签:pu int 题解 db mid dep tag WC2010 P4292

【乐正绫 AI】世末歌者「Cotton」

绫绫,有你AI的每一天,我都很幸福[大笑][大笑][大笑]

【乐正绫AI】世末歌者【砖厂浪人&TsingClouds】

绫绫,有你的每一天,我都很幸福[大笑][大笑][大笑]

思路

点分治 + 单调队列

01 分数规划 + 长链剖分 + 线段树。

首先看到分数形式求最值先考虑分数规划,二分答案。

现在的问题是:是否存在长度在 \([L, U]\) 之间的树上路径 \(S\) 使得 \(\frac{\sum\limits_{e \in S} v(e)}{|S|} \geq ans\)

化简得 \(\sum\limits_{e \in S} - ans |S| \geq 0\)

可以考虑给树上的每条边权值赋予一个当前二分出的变化量 \(\Delta\),这样直接判定是否存在权值和大于 \(0\) 的路径即可。

树上路径考虑点分治和长剖,这里点分治不好合并,长剖比较好写。

而且点分治常数应该挺大,虽然我的长剖跑不过

因为路径的合法长度是一个区间,所以最后查询答案需要区间查询,考虑用一棵线段树维护。

首先考虑继承答案。

类似重链剖分,考虑处理出每个结点的深子结点,然后按深子结点优先处理出每个结点的 dfs 序。显然一条深链的 dfs 序是连续的。

那么只需要把每个结点的答案存在对应的 dfs 序位置,就可以直接无痛继承了。

当然这里会增加一条边的权值,可以直接把它赋给当前结点的标记,最后从下到上累加标记就行。

考虑如何合并轻子结点的答案。根据长剖的复杂度分析,直接暴力线段树查询合并是可行的。

然后答案就直接分讨有拐点和无拐点的情况维护。

时间复杂度 \(O(n \log^2 n)\)

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef double db;

const int maxn = 1e5 + 5;
const int t_sz = maxn << 2;
const db inf = 1e18;
const db eps = 1e-7;

int n, el, eu, cur;
int dep[maxn], son[maxn], pos[maxn], tow[maxn];
vector<int> g[maxn], w[maxn];
db del, ans;
db f[maxn], tag[maxn];

namespace SGT
{
    #define ls (k << 1)
    #define rs (k << 1 | 1)

    db val[t_sz];

    void clear(int k, int l, int r)
    {
        val[k] = -inf;
        if (l == r) return;
        int mid = (l + r) >> 1;
        clear(ls, l, mid), clear(rs, mid + 1, r);
    }

    void push_up(int k) { val[k] = max(val[ls], val[rs]); }

    void update(int k, int l, int r, int p, db w)
    {
        if (l == r)
        {
            val[k] = max(val[k], w);
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(ls, l, mid, p, w);
        else update(rs, mid + 1, r, p, w);
        push_up(k);
    }

    db query(int k, int l, int r, int ql, int qr)
    {
        if ((l >= ql) && (r <= qr)) return val[k];
        int mid = (l + r) >> 1;
        db res = -inf;
        if (ql <= mid) res = max(res, query(ls, l, mid, ql, qr));
        if (qr > mid) res = max(res, query(rs, mid + 1, r, ql, qr));
        return res;
    }
}

void dfs1(int u, int fa)
{
    dep[u] = -1;
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i], d = w[u][i];
        if (v == fa) continue;
        dfs1(v, u);
        if (dep[u] < dep[v]) dep[u] = dep[v], son[u] = v, tow[u] = d;
    }
    dep[u]++;
}

void dfs2(int u, int fa)
{
    if (!pos[u]) pos[u] = ++cur;
    int pu = pos[u];
    tag[pu] = f[pu] = 0;
    if (son[u])
    {
        dfs2(son[u], u);
        tag[pu] += tag[pu + 1] + tow[u] - del;
        f[pu] = -tag[pu];
    }
    SGT::update(1, 1, n, pu, f[pu]);
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i], d = w[u][i];
        if ((v == fa) || (v == son[u])) continue;
        dfs2(v, u);
        int pv = pos[v];
        for (int j = 1; j <= dep[v] + 1; j++)
            if (el - j <= dep[u])
            {
                db val = SGT::query(1, 1, n, pu + max(1, el - j), pu + min(eu - j, dep[u]));
                ans = max(ans, f[pv + j - 1] + tag[pu] + tag[pv] + val + d - del);
            }
        for (int j = 1; j <= dep[v] + 1; j++)
            if (d + f[pv + j - 1] + tag[pv] - del > tag[pu] + f[pu + j])
            {
                f[pu + j] = d + f[pv + j - 1] + tag[pv] - del - tag[pu];
                SGT::update(1, 1, n, pu + j, f[pu + j]);
            }
    }
    if (dep[u] >= el) ans = max(ans, tag[pu] + SGT::query(1, 1, n, pu + el, pu + min(eu, dep[u])));
}

bool check(db x)
{
    SGT::clear(1, 1, n);
    ans = -inf, del = x;
    dfs2(1, 0);
    return (ans >= 0);
}

int main()
{
    scanf("%d%d%d", &n, &el, &eu);
    for (int i = 1, u, v, d; i <= n - 1; i++)
    {
        scanf("%d%d%d", &u, &v, &d);
        g[u].push_back(v), w[u].push_back(d);
        g[v].push_back(u), w[v].push_back(d);
    }
    dfs1(1, 0);
    db l = 0, r = 1e6;
    while (r - l > eps)
    {
        db mid = (l + r) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.3lf\n", l);
    return 0;
}

标签:pu,int,题解,db,mid,dep,tag,WC2010,P4292
From: https://www.cnblogs.com/lingspace/p/p4292.html

相关文章

  • Centos7下安装Dogtail GUI自动化测试工具并打开sniff工具过程中遇到的问题解决方法
    (目录)因为测试需要,需在Centos下进行liunxGUI软件自动化测试,所以用到了python的Dogtail库,继而使用Dogtail的sniff控件获取工具,但是遇到了很多问题记录如下。1环境Cent......
  • SPOJ LCMSUM 题解
    LCMSUM题意:求:\(\sum\limits_{i=1}^n\lim(i,n)\)数据范围:\(1\leqT\leq3\times10^5\),\(1\leqn\leq10^6\)。原式\(=\sum\limits_{i=1}^n\frac{i\timesn}{\gc......
  • 题解 CF678D【Iterated Linear Function】
    暴力解法。初学群论,可能写的不是很严谨,望大佬指正。problem\[g^{(n)}(x)=\begin{cases}x,&(n=0).\\f(g^{(n-1)}),&(n>0).\end{cases}\]其中\(f\)是一次函数。给出......
  • 【题解】CF848C Goodbye Souvenir
    冷漠和缄默思路cdq分治。有各种懂哥写了科技做法,比如树套树和二维分块,有点离谱。首先考虑答案的形式。令\(lst_i\)为\([1,i)\)中\(a_i\)最后一次出现的位置,则......
  • AGC060 题解
    Wow,ChristmasRound.--Tom66A.NoMajority(1300)结论:若一个序列有严格众数,则序列中必有两个相同数字位置之差为\(1\)或\(2\)。证明设序列长为$k$,则严格......
  • vue 使用echarts图表 setOption多次很卡问题解决
    项目场景:在开发ISM组态软件时,使用echarts图表,拖拽图表很卡。问题描述在vue中使用echarts使用setOption更新加载图形很慢原因分析:由于this.echartsView=echarts.init(view,......
  • Ubuntu Server20.04 sssd+samba4共享无法访问问题解决
    UbuntuServer20.04sssd+samba4共享无法访问问题解决报错: \\ipisnotaccessible排查:在samba的log里(/var/log/samba/log.ip)能看到winbinddnotrunning解决:#apt-getins......
  • IOI 2019 题解
    Day1A排列鞋子从前往后考虑每个位置\(i\),并找到与它匹配的最靠前的元素,将这两个元素放在最靠前的空位置,最后算一下逆序对个数即可。Day1B景点划分假设\(a\leb\le......
  • 【题解】CF893F Subtree Minimum Query
    那个……令姐……能以成亲为前提……和我交往吗(娇羞)集训完刚好开方舟春活,并且我刚好攒够了给令姐买衣服的石头,这真的是巧合吗?思路各种做法,但是有强化版。首先是naive......
  • 题解 P8294 [省选联考 2022] 最大权独立集问题
    Solution根据一些逝去的记忆可以得到一个DP状态:\(f_{u,x,y}\)表示\(u\)这棵子树,\(x\)从子树出去,\(y\)进来这棵子树。然后讨论一下状态转移,可以暴力枚举状态,暴力枚......