程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CF 574E(Bear and Drawing-2*n點陣畫樹)

CF 574E(Bear and Drawing-2*n點陣畫樹)

編輯:C++入門知識

CF 574E(Bear and Drawing-2*n點陣畫樹)


 

E. Bear and Drawing time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Limak is a little bear who learns to draw. People usually start with houses, fences and flowers but why would bears do it? Limak lives in the forest and he decides to draw a tree.

Recall that tree is a connected graph consisting of n vertices and n - 1 edges.

Limak chose a tree with n vertices. He has infinite strip of paper with two parallel rows of dots. Little bear wants to assign vertices of a tree to some n distinct dots on a paper so that edges would intersect only at their endpoints — drawn tree must be planar. Below you can see one of correct drawings for the first sample test.

\

Is it possible for Limak to draw chosen tree?

Input

The first line contains single integer n (1 ≤ n ≤ 105).

Next n - 1 lines contain description of a tree. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) denoting an edge between vertices ai and bi. It's guaranteed that given description forms a tree.

Output

Print Yes (without the quotes) if Limak can draw chosen tree. Otherwise, print No (without the quotes).

Sample test(s) input
8
1 2
1 3
1 6
6 4
6 7
6 5
7 8
output
Yes
input
13
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
output
No

 

 

這題要構造解

構造的解是這樣的

\

 

 

首先我們把葉子節點以及相連的鏈標記is_lef

然後對每個點統計分出的鏈的次數(分出一顆大子樹不計)

然後除鏈和Y形,點最多分出2個大子樹,否則無解

 

 

 

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (200000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n;
int edge[MAXN],pre[MAXN],next[MAXN],siz=1;
void addedge(int u,int v) {
	edge[++siz]=v;
	next[siz]=pre[u];
	pre[u]=siz;
}
void addedge2(int u,int v){addedge(u,v),addedge(v,u);}
int degree[MAXN]={0};

bool is_lef[MAXN]={0};
int legs[MAXN]={0};
void dfs(int x,int f)
{
	is_lef[x]=1;
	Forp(x) {
		int v=edge[p];
		if (v==f) continue;
		if (degree[v]<=2) dfs(v,x); //鏈 
	}
}



int main()
{
//	freopen(E.in,r,stdin);
//	freopen(.out,w,stdout);
	
	MEM(edge) MEM(pre) MEM(next)
	cin>>n;
	For(i,n-1) {
		int u,v;
		scanf(%d%d,&u,&v);
		addedge2(u,v);
		degree[u]++;degree[v]++;
	}
	
	//找鏈 
	For(i,n) {
		if (degree[i]==1) dfs(i,0);		
	}
	
	
	//找Y型 
	For(i,n) {
		Forp(i) {
			int v=edge[p];
			if (is_lef[v]) ++legs[i]; //一個點連出的鏈數 
		}
	}
	
	
	bool flag=1;
	
	
	For(i,n) {
		if (is_lef[i]) continue;
		int cnt=0;
		
		Forp(i) {
			int v=edge[p];
			if (!is_lef[v]&°ree[v]-min(legs[v],2)>=2)  //這個鄰居不是鏈也不是Y 
				++cnt;
		} 
		
		
		if (cnt>=3) { //只能向兩邊 
			flag=0;break;
		}
		
	}
	
	
	
	if (flag) puts(Yes);
	else puts(No);
	
	
	return 0;
}


 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved