2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet (树链剖分+构造)

本文主要是介绍2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet (树链剖分+构造)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://codeforces.com/gym/101611/problem/C
题意：给定一棵$n$个结点的树($n\le 100000$)，将其放入$1000000\ast 20$的方格中，使其任意两条边互不相交，求各个点的位置坐标。

看了题解才想到轻重链剖分。因为该方格的特点是x轴很长，y轴比较短，所以将其最长链往右放，剩下的往上放，也就是重儿子往右放，轻儿子往上放。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN=100010;
int k=1,x,y,head[MAXN],siz[MAXN],son[MAXN],fa[MAXN],X[MAXN],Y[MAXN];
struct Edge{int from,to,next;
}e[2*MAXN];
void addedge(int u,int v)
{e[k].from=u;e[k].to=v;e[k].next=head[u];head[u]=k++;
}void dfs1(int s)
{siz[s]=1;son[s]=0;for(int i=head[s];i;i=e[i].next){if(e[i].to!=fa[s]){fa[e[i].to]=s;dfs1(e[i].to);siz[s]+=siz[e[i].to];if(siz[e[i].to]>siz[son[s]])son[s]=e[i].to;}}
}void dfs2(int s)
{X[s]=x;Y[s]=y;//printf("!%d %d %d\n",s,x,y);if(son[s]==0)return ;y++;for(int i=head[s];i;i=e[i].next){if(e[i].to!=son[s]&&e[i].to!=fa[s]){dfs2(e[i].to);x++;}}y--;x++;dfs2(son[s]);
}int main()
{int n;scanf("%d",&n);for(int i=1;i<=n-1;i++){scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}dfs1(1);x=1;y=1;dfs2(1);for(int i=1;i<=n;i++)printf("%d %d\n",X[i],Y[i]);return 0;
}

这篇关于2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet (树链剖分+构造)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---