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

NOIP复习： --- 看到题想到的第一件事 树上问题树链剖分最无脑 后来证明我错了 --- 不过这题的确可以树链剖分啊 总体思路：枚举去掉哪条边，快速求出所有路径中最长距离 剩余距离的最大值只能有两种情况 - 不经过去掉的边的路径中最长的 - 经过去掉的边的路径中最长的 --- 现在考虑如何维护 只需树上维护以上两个信息 - 用一个树链剖分 $ \because $ 路径会被拆成 $ O(\log n) $ 段连续区间 $ \therefore $ 路径外的部分也会被拆成 $ O(\log n) $段连续区间 - 线段树维护一下 树上信息为 - 一个区间内边的路径长度 - 经过该区间内任意一条边的路径的最长长度（只需要询问叶子上的这个信息，但是由于是区间修改，区间上也要存） - 不经过该区间内某一条边的路径的最长长度（仍然只需要询问叶子上的这个信息） --- TLE了 --- 原因可能是线段树太慢了 怎么办呢？ 我们分步考虑怎么优化复杂度 subtask1：求路径长度 既然都剖过了，那么前缀和一下应该就搞定了吧 subtask2：路径修改a变量为一个值，路径外修改b变量为一个值，所有查询在修改之后 好问题。 将每次树上修改拆出来的区间存一下，转换为经典的序列问题 - $ O(n \log n) $ 次修改操作，将区间修改为同一个权值（预处理：把路径按长度从小到大排序） - $ O(n) $ 次查询，询问单点权值 - 所有查询在修改之后 用并查集搞一搞 ```cpp 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分 原因大概是内存不够，不能正确解决完全二叉树的情况 --- 我终于还是把这篇博客发出来了