Codeforces 573C. Bear and Drawing

题目
题意：有一棵树，然后有两行列无限的点。问这棵树能否画在点阵上，树的边不能相交

Solution

我们记只有一个点的子树为①。
记只有1个①的子树为①。
记有且仅有2个①的子树为②。
记有且仅有1个③或至少有1个②或至少有3个①的子树为③。
记恰好有2个③和若干小于③的子树为④。
记其他的子树为⑤。
只有当根不超过④时，才合法

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100001;
struct node{
	int to,ne;
}e[N<<1];
int n,i,h[N],num[N],sum[N][6],tot,x,y;
bool fl;
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
int calc(int u){
	if (sum[u][5] || sum[u][4] || sum[u][3]>2) return 5;
	if (sum[u][3]>1) return 4;
	if (sum[u][3] || sum[u][2] || sum[u][1]>2) return 3;
	if (sum[u][1]>1) return 2;
	return 1;
}
void dfs1(int u,int fa){
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=fa){
			dfs1(v,u);
			sum[u][num[v]]++;
		}
	num[u]=calc(u);
}
void dfs2(int u,int fa,int x){
	if (fl) return;
	sum[u][x]++;
	if (calc(u)<5){
		fl=1;
		return;
	}
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=fa){
			sum[u][num[v]]--;
			dfs2(v,u,calc(u));
			sum[u][num[v]]++;
		}
	sum[u][x]--;
}
void add(int x,int y){
	e[++tot]=(node){y,h[x]};
	h[x]=tot;
}
int main(){
	n=rd();
	for (i=1;i<n;i++) x=rd(),y=rd(),add(x,y),add(y,x);
	dfs1(1,0);dfs2(1,0,0);
	puts(fl?"Yes":"No");
}