Lomsat gelral CodeForces - 600E （树上启发式合并）
Youaregivenarootedtreewithrootinvertex1.Eachvertexiscolouredinsomecolour.Let'scallcolourcdominatinginthesubtreeofvertexviftherearenoothercoloursthatap...
树上启发式合并 (dsu on tree)
这个故事告诉我们，在做一个辣鸡出题人的比赛之前，最好先看看他发明了什么新姿势==居然直接出了道裸题参考链接：http://codeforces.com/blog/entry/44351（原文）http://blog.csdn.net/QAQ__QAQ/article/details/53455462...
loj516 DP一般看规律（set启发式合并）
题目：https://loj.ac/problem/516分析：每次将一个颜色更改为另一个颜色相当于将两个集合合并然后对于答案的更新，一个点插入到一个集合中，那么可能更新答案的就是其前驱节点或者后继节点所以直接用set启发式合并就ok了时间复杂度O(nlog^2n+m)loj516DP一般看规律（s...
【JZOJ5363】【NOIP2017提高A组模拟9.14】生命之树 Trie+启发式合并
题面45在比赛中，我只想到了45分的暴力。对于一个树中点对，相当于在他们的LCA及其祖先加上这个点对的贡献。那么这个可以用dfs序+树状数组来维护。100想法我想到了可能要用trie树来维护这个字符串的公共前缀。然后这就面临了两个很严重的问题。1.我对于每个子树都要建一个trie，所以这是\(O(n...
UOJ356 [JOI2017春季合宿] Port Facility 【启发式合并】【堆】【并查集】
题目分析：好像跑得很快，似乎我是第一个启发式合并的。把玩具看成区间。首先很显然如果有两个玩具的进出时间有$l1<l2<r1<r2$的关系，那么这两个玩具一定在不同的栈中间。现在假设一定有解，我们怎么得到答案呢？排序会使得计算变得方便，下面我们按照左端点排序。想象一条扫描线，从左往右...
Codeforces 600E Lomsat gelral （启发式合并）
Codeforces600ELomsatgelral（启发式合并）题目大意：一棵树，每个点有一个颜色，每一次询问在u节点为根的子树中，颜色出现次数最多的那些颜色的和。考虑启发式合并，每个节点开map，cnt[u][i]表示u节点为根的子树上，i颜色在出现多少次，sum[u][i]表示在当前子树中，恰...
Codeforces 600E Lomsat gelral（dsu on tree树上启发式合并）
题意给一颗有根树，节点有颜色，求每个点子树内出现次数最多的颜色的权值（有多个就是权值和）。1 ≤ n ≤ 105 1 ≤ ci ≤ n 权值题解考虑暴力的做法，对于每个节点直接遍历，将颜色放入桶，统计答案。这样复杂度是n2的。怎么去优化呢？可以看到每次遍历完一棵子树，我们都是把桶清空再重新遍历，其实...
Codeforces 600E :Lomsat gelral（启发式合并）
传送门题意：给一棵树，每个点有一个颜色，定义一个点的权值为其子树中最多的颜色（若有多个则是他们的和），求每个点的权值。题解：好题首先可以Splay启发式合并一波，可以得到理论上的O(nlogn)复杂度，不过有一种跑得飞快的启发式合并方法，（实际复杂度也是O(nlogn)的）。考虑对这棵树树链剖分。显...
Codeforces 600E Lomsat gelral [dsu on tree(树上启发式合并)]
题意给出一棵树，1为根节点，每个点都有一个颜色。求每个点所在子树内所有出现次数最多的颜色的和。n<=100000分析新学习了一种姿势叫dsuontree，大概意思就是树上启发式合并吧。dsuontree大概是用来解决这样一类问题：需要多次查询某棵子树内的某个值（必须要离线）。像这题就是需要查询...
ARC 086 E - Smuggling Marbles(dp + 启发式合并)
题意Sunke有一棵\(N+1\)个点的树,其中\(0\)为根,每个点上有\(0\)或\(1\)个石子,Sunke会不停的进行如下操作直至整棵树没有石子:把\(0\)上面的石子从树上拿走放入口袋;把每个点上的石子移到其父亲上;对于每个点,若其石子数\(≥2\),则移除该点所有石子(不放入口袋)。求对...
BZOJ 2733 [HNOI2012]永无乡 (权值线段树启发式合并+并查集)
题意：n<=1e5的图里，在线连边、查询某连通块第k大思路：练习线段树合并的好题，因为依然记得上一次启发式合并trie的时候内存爆炸的恐怖，所以这次还是用了动态开点、回收听说启发式合并splay更快QAQ，学会了试试代码：#include<iostream>#include<...
2018.10.14 loj#516. DP 一般看规律（启发式合并）
传送门注意到一种颜色改了之后就不能改回去了。因此可以启发式合并。每次把小的合并给大的。这样每个数最多被合并logloglog次。如果维护一棵比较下标的平衡树的话，对于答案有贡献的就是每个数与前驱和后继的差值。于是就用setsetset实现啦。代码：#include<bits/stdc++.h&...
2018.12.22 bzoj3277: 串（后缀自动机+启发式合并）
传送门跟这道题是一模一样的。于是本蒟蒻又写了一遍10min1A庆祝代码：#include<bits/stdc++.h>#defineriregisterintusingnamespacestd;constintN=2e5+5;typedeflonglongll;intT,k;string...
[Codeforces600E] Lomsat gelral（树上启发式合并）
[Codeforces600E]Lomsatgelral（树上启发式合并）题面给出一棵N个点的树，求其所有子树内出现次数最多的颜色编号和。如果多种颜色出现次数相同，那么编号都要算进答案N≤100000分析树上启发式合并，用map记录颜色出现次数，合并的时候更新最多的出现次数和编号和。注意合并时的下标...
codeforces600E Lomsat gelral -- 树上启发式合并
显然加入和删除点可以O(1)维护。先做一次树剖，然后从根开始dfs一遍。dfs到一个点时加入答案。对于每个点如果是轻儿子退出时删除，否则不删除。统计答案时暴力dfs一遍所有轻儿子。因为一个点到根路径上只有O(logn)条轻边，所以最多只会被统计O(logn)次。时间复杂度为O(nlogn)。代码：#...
Codeforces 600E Lomsat gelral （树上启发式合并）
题目链接Lomsatgelral占坑……等深入理解了再来补题解……#include<bits/stdc++.h>usingnamespacestd;#definerep(i,a,b)for(inti(a);i<=(b);++i)typedeflonglongLL;constintN...
Codeforces 600E. Lomsat gelral(树上启发式合并)
题意：n个点的有根树，以1为根，每个点有一种颜色。我们称一种颜色占领了一个子树当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和。题解：树上启发式合并,[Tutorial]Sack(dsuontree)-Codeforces#include<bits/stdc++.h&...