icontofig | 发布于 2020-04-16 22:28:40 | 阅读量 467 | 树链剖分
发布于 2020-04-16 22:28:40 | 树链剖分

题目大意

给出一棵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 x,int y){
    p[now] = {x,y};
    if(!son[now])return;
    work(son[now],x + siz[now] - siz[son[now]],y);
    int res = 0;
    for(auto it : g[now]){
        if(it == f[now] || it == son[now])continue;
        work(it,x + res,y+1);
        res += siz[it];
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i < n;++i){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    work(1,1,1);
    for(int i = 1;i <= n;++i){
        cout << p[i].x << " " << p[i].y << "\n";
    }
    return 0;
}



内容更新于: 2020-04-16 22:28:40
链接地址: http://blog.leanote.com/post/icontofig/2017-2018-ACM-ICPC-NEERC-Moscow-Subregional-Contest-C.-Carpet

上一篇: ZOJ 4086 Little Sub and a Game 线性基博弈

下一篇: 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest I . Infinite Gift

467 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航