UOJ#150 运输计划 树链剖分做法

2017-12-09 08:53:02


NOIP复习:


看到题想到的第一件事

树上问题树链剖分最无脑

后来证明我错了


不过这题的确可以树链剖分啊

总体思路:枚举去掉哪条边,快速求出所有路径中最长距离

剩余距离的最大值只能有两种情况

  • 不经过去掉的边的路径中最长的

  • 经过去掉的边的路径中最长的


现在考虑如何维护

只需树上维护以上两个信息

  • 用一个树链剖分

    $ \because $ 路径会被拆成 $ O(\log n) $ 段连续区间

    $ \therefore $ 路径外的部分也会被拆成 $ O(\log n) $段连续区间

  • 线段树维护一下

树上信息为

  • 一个区间内边的路径长度

  • 经过该区间内任意一条边的路径的最长长度(只需要询问叶子上的这个信息,但是由于是区间修改,区间上也要存)

  • 不经过该区间内某一条边的路径的最长长度(仍然只需要询问叶子上的这个信息)


TLE了


原因可能是线段树太慢了

怎么办呢?

我们分步考虑怎么优化复杂度

subtask1:求路径长度

既然都剖过了,那么前缀和一下应该就搞定了吧

subtask2:路径修改a变量为一个值,路径外修改b变量为一个值,所有查询在修改之后

好问题。

将每次树上修改拆出来的区间存一下,转换为经典的序列问题

  • $ O(n \log n) $ 次修改操作,将区间修改为同一个权值(预处理:把路径按长度从小到大排序)

  • $ O(n) $ 次查询,询问单点权值

  • 所有查询在修改之后

用并查集搞一搞

int find(int x,int end,int val)
{
    if(!c[x])c[x]=val;
    if(next[x]<=end)return next[x]=find(next[x],end,val);
    return x;
}
for(int i=m;i>=1;i--)
{
    find(l[i],r[i],val[i]);
}

代码十分简洁

主要思路是记录每个点右边第一个未修改的点,逆序处理所有修改操作,每次暴力修改,并进行类似并查集的路径压缩

复杂度应该是对的(一个 $ log $ )

光荣97分 原因大概是内存不够,不能正确解决完全二叉树的情况


我终于还是把这篇博客发出来了