[dsu on tree][学习笔记] - Candy? - 博客园 题单: 也称:树上启发式合并 可以解决绝大部分不带修改的离线询问的子树查询问题 流程: 1.重链剖分找重儿子 2.sol:全局用桶或者数据结构存信息. ①递归所有的轻儿子,回溯前删除贡献 ②递归重儿子,不删除贡献 ③暴力找所有轻儿子,加入贡献 ④更新x的答案 ⑤如果x是父亲的轻儿子,再把整个子树贡献删除(信息只有子树的,有时可以不用再dfs去重,可以直接清空) 正确性: 一个点的轻儿子会暴力更新到所有信息,重儿子链不会删除贡献

题目大意: 一颗树,想要在树链上添加同一物品,问最后每个点上哪个物品最多. 解题思路: 1.线段树合并 假如说物品数量少到可以暴力添加,且树点极少,我们怎么做. 首先在一个树节点上标记出哪些物品有多少,寻找道路上的节点暴力添加. 而如果节点比较多,我们使用树上差分u+1,v+1,lca-1,fa[lca]-1向上求和就得到了答案 而颜色较多呢,和刚才唯一不同就在于向上求和时不要用数组,用线段树合并就好了(记录线段树区间的最大值与最大位置) 废点的回收是非常实用的^_^ 时间复杂度O(nlogn)

题意: 一棵树,询问一个子树内出现次数$≥k$的颜色有几种 强制在线见上一道 用莫队不知道比分块高到哪里去了,超好写不用调7倍速度!!! 可以用分块维护出现次数这个权值,实现$O(1)-O(\sqrt{N})$修改查询 [update 2017-03-22]还可以用dsu on tree做,并不想再写了... #include <iostream> #include <cstdio> #include <algorithm> #include <cstring&g

题目链接 \(Description\) 给定一棵树,每条边上有一个字符(a~v).对每个节点,求它的子树中一条最长的路径,满足 路径上所有边上的字符可以重新排列成一个回文串.输出其最长长度. \(n\leq 5\times10^5\). \(Solution\) 可以构成回文串,即要么所有字符都出现了偶数次,要么有一个出现了奇数次.其余都出现了偶数次. 转化为异或!把每个字符c(0~21)映射到1<<c上去. 令\(s[x]\)表示根节点到\(x\)路径上边权的异或和.那么路径\((u,v)

dsu on tree,又名树上启发式合并.重链剖分,是一类十分实用的trick,它常常可以作为一些正解的替代算法: 1.DFS序+线段树/主席树/线段树合并 2.对DFS序分块的树上莫队 3.长链剖分(但复杂度会多一个log) 4.点分治(通常可以做有根树的点分治) 重链剖分的概念,用一个DFS找到每个点最大的一个儿子,作为它的重儿子,并将它标记.则从上到下一段连续的标记点就成为一条重链. 重链剖分有一个常用的性质:每个点到根的路径上,至多经过$O(\log n)$条重链.点分治.树链剖分都用

题目描述 一棵树有$n$个结点,每个结点都是一种颜色,每个颜色有一个编号,求树中每个子树的最多的颜色编号的和. 这个题意是真的窒息...具体意思是说,每个节点有一个颜色,你要找的是每个子树中颜色的众数(可能有多个),比如子树中有$3个2,3个1,3个5,那么2,1,5都是众数,答案为2+1+5=8$. 思路 做法一: 线段树合并.权值线段树覆盖颜色$1->100000,用sum$表示颜色最多出现的次数,$ans$表示答案.分$3种情况pushup$即可. 左右子树$sum$相等 左边$>$右边

dsu on tree. \(\rm 0x01\) 前言\(\&\)技术分析 \(\bold{dsu~on~tree}\),中文别称"树上启发式合并"(虽然我并不承认这种称谓),大概是一种优雅的暴力,并且跟\(dsu\)毫无关系.于是我打算叫他\(\bold{Elegantly~Direct~Counting~on~Tree}\),"优雅的树上暴力统计". 严格来说,\(\bold {EDCT}\)解决的问题范围并不广泛: 1.维护子树信息: 2.不能带修改

前言 一次模拟赛的\(T3\):传送门 只会\(O(n^2)\)的我就\(gg\)了,并且对于题解提供的\(\text{dsu on tree}\)的做法一脸懵逼. 看网上的其他大佬写的笔记,我自己画图看了一天才看懂(我太蒻了),于是就有了这篇学习笔记. 概念篇/基础运用 算法简介 现在考虑这样一类树上统计问题: 无修改操作,询问允许离线 对子树信息进行统计(链上的信息在某些条件下也可以统计) 树上莫队?点分治? \(\text{dsu on tree}\)可以把它们吊起来打! \(\text{

简介 对于一颗静态树,O(nlogn)时间内处理子树的统计问题.是一种优雅的暴力. 算法思想 很显然,朴素做法下,对于每颗子树对其进行统计的时间复杂度是平方级别的.考虑对树进行一个重链剖分.虽然都基于重链剖分,但不同于树剖,我们维护的不是树链. 对于每个节点,我们先处理其轻儿子所在子树,轻子树在处理完后消除其影响.然后处理重儿子所在子树,保留其贡献.然后再暴力跑该点的轻子树,统计该点子树的最终答案.如果该点子树是轻子树,则消除该子树的影响,否则保留.用代码描述的话,大概是这个流程: void d

题目传送门(内部题103) 输入格式 第一行一个数$n$,表示结点的个数. 第二行$n–1$个数,第$i$个数是$p[i+1]$.$p[i]$表示结点$i$的父亲是$p[i]$.数据保证$p[i]<i$. 第三行$n$个数,$a[1],a[2],...,a[n]$,表示关卡表.数据保证这是一个排列. 第四行$n$个数,$x[1],x[2],...,x[n]$,表示结点的权值. 输出格式 输出一个数表示答案.即对于所有可能的回合,你们能获得的总收益是多少. 数据范围与提示 对于$20\%$的数据,

dsu on tree 对于树进行轻重链剖分,对于节点 $x$ ,递归所有轻儿子后消除其影响,递归重儿子,不消除其影响. 然后对于所有轻儿子的子树暴力,从而得到 $x$ 的答案. 对于要消除暴力消除即可. 可以发现如果暴力到点 $u$ 必然是其 $u$ 到根的轻边数量,从而时间复杂度除在统计每个节点答案时其余时间复杂度为 $O(n\log n)$ . CF 600E Lomsat gelral 模板题,按上述过程模拟即可. #include<iostream> #include<cstd

D. Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths CF741D 题意: 一棵有根树,边上有字母a~v,求每个子树中最长的边,满足这个边上的所有字母重拍后可以构成回文 发明者自己出的题...orz 由于本来知道就是dsu on tree,所以还是想出来了 首先点分治是没法做了,这是有根树 写成二进制,两条链合起来构成回文\(\rightarrow\)异或和为0或者只有一位是1 一开始困惑于只处理到当前根的异或和的话,随着当前

传送门 题意: 一棵树,询问某棵子树指定深度的点能否构成回文 当然不用dsu on tree也可以做 dsu on tree的话,维护当前每一个深度每种字母出现次数和字母数,我直接用了二进制.... 一开始dfs没有判断重儿子T了一次 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using names

十几天前看到zyf2000发过关于这个的题目的Blog, 今天终于去学习了一下 Codeforces原文链接 dsu on tree 简介 我也不清楚dsu是什么的英文缩写... 就像是树上的启发式合并 用到了\(heavy-light\ decomposition\)树链剖分 把轻边子树的信息合并到重链上的点里 因为每次都是先dfs轻儿子再dfs重儿子,只有重儿子子树的贡献保留,所以可以保证dfs到每颗子树时当前全局维护的信息不会有别的子树里的,和莫队很像 算法过程 find the BigC

近几天跟着dreagonm大佬学习了\(dsu\ on\ tree\),来总结一下: \(dsu\ on\ tree\),也就是树上启发式合并,是用来处理一类离线的树上询问问题(比如子树内的颜色种数)的不二法宝.它不仅好想好写,还有着\(O(nlogn)\)的优秀时间复杂度(划重点). 结合一道例题来讲吧: CF600E Lomsat gelral 题目大意: 一棵树有\(n(n\leqslant 10^5)\)个结点,每个结点都是一种颜色,每个颜色有一个编号,求树中每个子树的最多的颜色编号的和

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ266.html 题解 首先我们可以直接暴力 $O(n^2)$ 用 sg 函数来算答案. 对于一个树就是枚举一下从根出发到哪一个节点为止的路径被删掉了,剩下所有的子树的sg值xor起来,对于每一个路径后的答案取一个 mex . 我们考虑快速的做这个过程. 直接写个 Trie 再 DSU on tree 就好了,只要支持查询 mex 和整棵 trie 对某一个值 xor 这两种操作就好了. 时间复杂度 $O

先瞎扯几句 说起来我跟这个算法好像还有很深的渊源呢qwq.当时在学业水平考试的考场上,题目都做完了不会做,于是开始xjb出题.突然我想到这么一个题 看起来好像很可做的样子,然而直到考试完我都只想出来一个莫队的暴力.当时我想知道有没有比莫队更优的做法,和zbq讨论了半天也只能搞出一个$O(nlog^2n)$的平衡树启发式合并 然后!!我就把这题出给校内互测了!!没错,当时是用莫队当的标算! 结果!mjt用一个假的$O(n)$算法艹过去了因为数据特别水 后来我打算把这题出给另一场比赛,结果到了前一天

原文链接https://www.cnblogs.com/zhouzhendong/p/LuoguP4482.html 题意 给定一个字符串 S,有 q 次询问,每次给定两个数 L,R ,求 S[L...R] 的最长前后缀. $$q,|S|\leq 2 \times 10 ^ 5$$ 题解 真是一道有趣的字符串题. 首先我们给 S 建出 SAM ,并用线段树合并预处理出每一个节点的 Right 集合. 我们要做的是找到最大的 $p$ 满足 $p<R, S[L...p] = S[R-p+L...R]

题目链接: Codeforces741D 题目大意:给出一棵树,根为$1$,每条边有一个$a-v$的小写字母,求每个点子树中的一条最长的简单路径使得这条路径上的边上的字母重排后是一个回文串. 显然如果一条路径上的字母重排后是回文串,那么最多有一个字母有奇数个.我们用$2^{22}$的一个二进制来记录有哪些字母有奇数个.剩下的只需要$dsu\ on\ tree$来求每个点的答案即可.对于每个点记录它到根的路径上的字母的二进制状态,显然位于一个点两个不同子树中的点的状态异或起来就是这两个点间路径的二

BZOJ 题目的限制即:给定一棵树,只能任选一个连通块然后做背包,且每个点上的物品至少取一个.求花费为\(m\)时最大价值. 令\(f[i][j]\)表示在点\(i\),已用体积为\(j\)的最大价值. 如果物品数量为\(1\),那就是一个树形依赖背包(选儿子必须选父亲),用DFS序优化转移:\(f[i][j]=\max(f[i+1][j-v_i]+w_i,\ f[i+sz_i][j])\)(选该节点就可以从上一个点,即子树内转移,否则只能从另一棵子树转移),复杂度\(O(nm)\). 物品数量