http://codeforces.com/contest/761/problem/E
题意:
给出一棵树,现在要把这棵树上的结点放置在笛卡尔坐标上,使得每一条边与x轴平行或者与y轴平行。输出可行解,即每个点放置的坐标。
思路:
一开始我想,这个每条边的边长都是可长可短的,好像很麻烦啊。
做法还是很巧妙的,因为最多也就30个点,所以我们直接让该点连接的边未len长度,然后dfs它的子节点并使它的子节点的边长为len/2。你会发现,这样线段就不会相交了。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std; const int maxn=+; int n;
vector<int> g[maxn];
int vis[maxn];
long long ans_x[maxn],ans_y[maxn]; int dx[]={,-,,};
int dy[]={-,,,}; void dfs(int u,int fa_dir,long long dir)
{
vis[u]=;
int k=;
for(int i=;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
if(k==-fa_dir) k++;
ans_x[v]=ans_x[u]+dir*dx[k];
ans_y[v]=ans_y[u]+dir*dy[k];
dfs(v,k,dir/);
k++;
}
}
} int main()
{
while(~scanf("%d",&n))
{
bool flag=true;
for(int i=;i<=n;i++) g[i].clear();
for(int i=;i<n-;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
if(g[u].size()> || g[v].size()>) flag=false;
}
if(!flag) {puts("NO");continue;}
memset(vis,,sizeof(vis));
ans_x[]=; ans_y[]=;
dfs(,-,<<);
puts("YES");
for(int i=;i<=n;i++)
printf("%lld %lld\n",ans_x[i],ans_y[i]);
}
return ;
}