http://codeforces.com/gym/101611/problem/C 题意：给定一棵 n n n个结点的树( n ≤ 100000 n\leq100000 n≤100000)，将其放入 1000000 ∗ 20 1000000*20 1000000∗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; }