Tag-树链剖分

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-04-16 22:28:40 |  0 Comments  |  树链剖分

2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet

题目大意

给出一棵n个节点的树,要求将这个树的所有节点映射到一张1000000*20的横向表格里,要求保持原先的连边映射成的相连线段不能有交叉。

输出一种方案,要求将所有的树上节点的坐标输出。

题解

行数最多只有20行,所以要考虑最大行数控制在log2n以内。所以就要想树上的什么东西一定小于小于等于log2n。

学过树链剖分的话不难想到,对一个树进行重链剖分的话,所有点向下的轻链长度一定小于等于log2n,树链剖分的复杂度就是基于这个性质证明的。这个性质的证明并不难想,因为对于一个节点x,其轻儿子的子树大小一定不会超过siz[x]/2,否则这个儿子就是重儿子了。

然后就可以明白,要先对树进行重链剖分,对每个节点now把重儿子和自己放在同一行上,轻儿子放在下一行,重儿子和自己的距离间隔为siz[now]-siz[son[now]],第一个轻儿子v1放在(x[now],y[now]+1),第二个轻儿子v2放在(x[now]+siz[v1],y[now]+1),第三个轻儿子v3放在(x[now]+siz[v1]+siz[v2],y+1),以此类推。

因为横向的列数极多,所以横向不会出现问题,又由轻链长度的性质,纵向不会不会超过20.上述的放节点的留空就是为了使得边不会交叉采取的方案。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
vector<int>g[maxn];
int son[maxn],siz[maxn],f[maxn];
struct point{
    int x,y;
}p[maxn];
void dfs(int now,int fa){
    siz[now] = 1;
    son[now] = 0;
    f[now] = fa;
    for(auto it : g[now]){
        if(it == fa)continue;
        dfs(it,now);
        siz[now] += siz[it];
        if(siz[it] > siz[son[now]])
            son[now] = it;
    }
    return;
}
void work(int now,int 
 2020-04-05 16:24:36 |  0 Comments  |  dsu on tree 树链剖分

CodeForces 600E.Lomsat gelral dsu on tree 树上启发式合并

Example

15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

题目大意

给出一棵有根树,树上每个点有一个颜色,求问以每一个节点x为根的子树内数量最多的颜色的编号的和sum为多少。

题解

如果暴力统计的话,时间复杂度将会成为O(n2),这是我们没办法接受的。

貌似可以搞什么线段树合并还有莫队什么的。

但是复杂度好像依旧还是太高,于是就有这么一个神奇的东西叫dsu on tree,中文名叫树上启发式合并。

dsu实际上是并查集的问题,但这个算法并不是什么树上并查集,而是借鉴了并查集中启发式合并优化的思想,将这个思想运用到了树上。

结合树链剖分的性质,将所有的树链分为轻链和重链后,对于每一个子树的根节点rt:轻链子节点sq,递归进入计算以sq为根的子树的答案,但是不保存,递归结束时清空;重链子节点son,递归进入计算以son为根的子树的答案,递归结束时不清空,作为rt为根节点的子树的基础答案。

之后对于以rt为根节点的子树,在重链子节点son的子树提供的基础答案上,再暴力计算该子树其它所有轻链子树和rt节点本身的答案,与刚刚的基础答案合并,可以解算出以rt为根节点的子树的答案。

通过树链剖分的轻重链性质,不难证明答案的复杂度应该为O(nlog2n),因为所有节点被访问的次数至多为log2n次。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int x,y;
typedef long long ll;
ll ans[maxn],c[maxn],sum,mx;
int son[maxn],siz[maxn],f[maxn],cnt[maxn];
vector<int>g[maxn];
int n,s;
void dfs(int now,int fa){
    f[now] = fa;
    siz[now] = 1;
    for(auto it : g[now]){
        if(it == fa)continue;
        dfs(it,now);
        siz[now
Title - Artist
0:00