首页 > 其他分享 >2023.8.20学长分享

2023.8.20学长分享

时间:2023-08-20 10:22:35浏览次数:42  
标签:20 分治 离线 学长 2023.8 DP

Exeabow_sky

点分治

树上路径统计或最优化。(无根树)

找重心,分别考虑子树,标 vis。复杂度 O(nlogn)

路径合并信息。

对于较多次的查询可以用点分树;或离线,一次点分治处理完。

[CSP-S2022 T4]

也可点分治。

对于 k=2,对链在点分治中维护信息,离线;对分治中心 h,对两子树中点 a,b,做 like-DP,在一次 DFS 中算出,再算出答案。

但对于 k=3 呢?稍微预处理一下,做细节上的处理。

边分治

同样是找重心。但要做一些特殊处理,加入一些 0 权边与虚点(转二叉树)。

感觉不如点分治

长链剖分

x 的子树中距离 x 距离为 d 的个数。长剖优化 DP。

标签:20,分治,离线,学长,2023.8,DP
From: https://www.cnblogs.com/Zaunese/p/17643584.html

相关文章

  • P1 P2508 [HAOI2008]圆上的整点
    [HAOI2008]圆上的整点23.3.22WE.真是一道神题,特别是对于刚得了甲流滚回家摆烂从而有时间乱看而恰巧这几天上课刚学复数的我。一直很好奇复数到底是什么,昨天晚上刷B站学习偶然看到了一个解释虚数的视频,结果也没看懂,只听说乘上一个\(i\)相当于旋转\(90^{\circ}\),一想还真是!......
  • 我的2023暑假青岛3天2晚旅游归来
    本博客原文地址:https://ntopic.cn/p/2023081201/附:我的青岛旅游计划参见之前的文章:我的2023暑假青岛3天2晚旅游计划本文主要分享一下我的旅游体验和个人感受,纯属个人主观感觉,若有失偏颇,请留言或者发邮件给我,非常感谢~总体体验感觉:很不错先上总结,后面在详细介绍,如果还没有去过......
  • 在 win10 2021 LTSC 上安装配置 wsl2 和 ubuntu
    在win102021LTSC上安装配置wsl2和ubuntu的过程:win10系统启用wsl2:wsl--install----no-distribution(安装wsl2,会自动打开系统feature:wsl子系统,虚拟机平台.不再需要去控制面板--启用windows特性)设置wsl默认版本为wsl2:wsl--set-defa......
  • VS2015项目.net-framework-4.5.2升级或新建项目无法选择framework 4.6.2(解决办法)
    VS2015里面没有.NETFramework4.6.2VS2015默认安装的目标框架最高是.NETFramework4.6.1,但是我的项目里面某些NuGet软件包更新需要依赖.NETFramework4.6.2,项目就需要升级到目标框架.NETFramework4.6.2VS2015项目无法选择framework4.6.2的解决办法:第一步:系统环境安装.NET......
  • 巨杉数据库荣获2023胡润中国元宇宙潜力企业未来之星
    巨杉数据库凭借其在分布式文档型数据库领域的技术实力和创新能力,再次荣获2023胡润中国元宇宙潜力企业榜未来之星称号。近期,第二届胡润中国元宇宙高峰论坛暨《2023胡润中国元宇宙潜力企业榜》发布活动在广州南沙举办。作为国内基础软件的代表性厂商,巨杉数据库凭借其在分布式文档型......
  • 朝花夕拾:NHOI 2022 T6
    原题题意:题目描述给定一颗树有\(n\)个结点,每个结点上有一个权值\(a_i\),对于每条至少包含两个点的简单路径,它的贡献为路径上点的数量(包括端点)\(\times\)路径上所有点的\(a_i\)的最大公约数(gcd)。求所有简单路径的贡献之和,对\(998244353\)取模。......
  • 2023年8月16日
       今天早上起来背了10个英语单词,然后学习了一个小时的java,写了一会英语阅读,然后和朋友出去打了两个小时的羽毛球,最后写了一会作业。    明天打算看一小时的电视剧,然后和朋友出去玩一会,打一两个小时的篮球,最后晚上练一小时的字,然后学习一小时的java。......
  • 2023年8月18日
        今天早上起来背了10个英语单词,然后学习了一个小时的java,写了一会英语阅读,然后和朋友出去打了两个小时的羽毛球,最后写了一会作业。    明天打算看一小时的电视剧,然后和朋友出去玩一会,打一两个小时的篮球,最后晚上练一小时的字,然后学习一小时的java。......
  • 2023年8月17日
    今天早上起来背了10个英语单词,然后学习了一个小时的java,写了一会英语阅读,然后和朋友出去打了两个小时的羽毛球,最后写了一会作业。    明天打算看一小时的电视剧,然后和朋友出去玩一会,打一两个小时的篮球,最后晚上练一小时的字,然后学习一小时的java。......
  • 2023年8月19日
        今天早上起来背了10个英语单词,然后学习了一个小时的java,写了一会英语阅读,然后和朋友出去打了两个小时的羽毛球,最后写了一会作业。    明天打算看一小时的电视剧,然后和朋友出去玩一会,打一两个小时的篮球,最后晚上练一小时的字,然后学习一小时的java。......