[Codeforces] 761E. Dasha and Puzzle

題目連結:http://codeforces.com/problemset/problem/761/E

---

一開始以為邊長只能是一www
會發現節點才30個，那我們可以簡單的安排每個深度的邊長$2^{55-d_i}$這樣的話，因為$\sum_{i=0}^{n-1}2^i < 2^n$，所以絕對不會疊在一起，而且最大也就$2^{56} \leq 10^{18}$長度。接著就DFS下去把邊安排一下就好了XD

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
typedef pair<lld,lld> PLL;
#define FF first
#define SS second
const int N = 30 + 5;

lld dx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0};
int inv[]={1, 0, 3, 2, 5};

vector<int> G[N];
PLL ans[N];
int dep[N];
void dfs(int,int,int,PLL);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n-1;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	bool flag = false;
	for(int i=1;i<=n;i++) if(G[i].size() > 4){
		flag = true;
	}
	if(flag){
		cout<<"NO\n";
		return 0;
	}
	cout<<"YES\n";
	dep[1] = 0;
	dfs(1, 1, 4, {0LL, 0LL});
	for(int i=1;i<=n;i++) cout<<ans[i].FF<<" "<<ans[i].SS<<'\n';
	return 0;
}

void dfs(int w, int f, int pre, PLL pos){
	ans[w] = pos;
	dep[w] = dep[f]+1;
	int _ = 0;
	for(auto i: G[w]){
		if(i==f) continue;
		if(_==inv[pre]) _++;
		PLL newpos = pos;
		newpos.FF += dx[_]<<(55-dep[w]);
		newpos.SS += dy[_]<<(55-dep[w]);
		dfs(i, w, _, newpos);
		_++;
	}
}