打酱油 同构

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

给定2个树A和B，保证A的节点个数>=B的节点个数。

现在你需要对树A的边进行二染色。

一个好的染色方案，指不存在一个树A中的连通块，同时满足以下2个条件

1. 其中只有同色的边

2. 和B同构。两个树同构是指，存在一个一一映射（既是单射又是满射），将树B的各节点映射到不同的树A的节点，使得原来在树B中相邻的点，在映射后，仍相邻。

问是否存在一种好的染色方案。

输入

第一行一个整数T (1<=T<=10)，表示数据组数。

接下来是T组输入数据，测试数据之间没有空行。

每组数据格式如下：

第一行一个整数N ，表示树A的节点总数。

接下来N-1行，每行2个数a, b (1 <= a, b <= N)表示树A的节点a和b之间有一条边。

接下来一行，一个整数M(1 <= M <= N)，表示树B的节点总数。

接下来M-1行，每行2个数a, b (1 <= a, b <= M)表示树B的节点a和b之间有一条边。

输出

对每组数据，先输出“Case x:”，x表示是第几组数据，然后接“YES”/“NO”，表示是否存在所求的染色方案。

数据范围

小数据：1 <= N <= 20

大数据：1 <= N <= 1000000

样例解释

无论如何染色，只要从A中挑一条边就行了。

样例输入

1
3
1 2
2 3
2
1 2

样例输出

Case 1: NO

唉，第一题这么简单，居然没想出来。差距有点大啊。

染色的方法是按层次交替染色，则对于b树大于一层时，必定是没有同构且同色的连通块。所以只需要考虑只有一层的时候的情况。当只有一层b数上有y条边，则若a数上有节点的子节点数大于等于 2y-1时，就会有相同颜色的连通块了。

#include <iostream>
using namespace  std;
int ap[1001000],bp;

int main(){
	int T,N,M ,l,n,p,q, t = 1;
	cin>>T;
	while(T --){
		n = 0;
		cin >>N ;
		l = 0;
		while(--N){
			cin>>p>>q;
			if(p != l){
				ap[++n] = 0;
				l = p;
			}
			ap[n]++;	
		}
		cin>>M;
		bp = 0;
		while (--M)
		{
			cin>>p>>q;
			if(p == 1)
				bp ++;
			else
				l = -1;//l为-1时，则表示其为一层
		}
		printf("Case %d:",t++);
		if( l == -1)
			cout<<"Yes\n"<<endl;
		else{
			for(l = 0;l<n;l++){
				if(ap[l] >= 2*bp-1){
					l = -1;break;
				}
			}
			if(l == -1)cout<<"No\n"<<endl;
			else cout<<"Yes\n"<<endl;
		}
	}
	return 0;
}