0.75 seconds
256 megabytes
standard input
standard output
You are given two trees with the same number of leaves L, your task is to merge the two trees' leaves in a way that ensures the following:
- The number of colors needed to color the resulting graph such that no two adjacent nodes share the same color is minimum.
- Each leaf in the first tree is merged into exactly one leaf from the second tree.
- Each leaf in the second tree is merged into exactly one leaf from the first tree.
- Nodes other than leaves are not merged.
Note that by merging two leaves a and b, the resulting node will have both edges of a and b.
The first line of input contains one integer N (3 ≤ N ≤ 105), the number of nodes in the first tree.
Then follows N - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ N), the indices of the nodes connected by the ith edge in the first tree.
The next line contains an integer M (3 ≤ M ≤ 105), the number of nodes in the second tree.
Then follows M - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ M), the indices of the nodes connected by the ith edge in the second tree.
It is guaranteed that the two trees will have the same number of leaves L.
On a single line print the number of colors needed to color the resulting graph.
Followed by L lines, the ith line of them contains two integers u and v (1 ≤ u ≤ N)(1 ≤ v ≤ M), the indices of the leaves to be merged, where u is a leaf in the first tree, and v is a leaf in the second tree.
If there’s more than one possible solution, print any of them.
3
1 2
1 3
3
3 1
2 3
2
2 1
3 2
4
1 2
2 3
3 4
3
3 1
1 2
3
4 2
1 3
- A tree of N nodes is a connected undirected graph with N - 1 edges.
- A node is a leaf if and only if it is connected to at most one other node.
In the first sample, the two trees can be illustrated as follows:
After merging node 2 from first tree with node 1 from the second tree, and node 3 from the first tree with node 2 from the second tree, the resulting graph is illustrated in the figure below:
The minimum number of colors required to satisfy the problem constraints is 2.
【分析】给你两棵树，他们的叶子节点个数都为L，现在要将两棵树合并，方法是只合并叶子结点，即一一对应，合并后两个叶子结点就成了一个节点，两棵树即成了
一个有环图。然后给节点染色，相邻节点染不同颜色，问如何合并使得颜色数最少。
首先得想到一点，对于任何一个节点，他是可以与对面任一节点合并的。那么我们考虑一个合并后的一条支路（两个叶子结点合并后形成的），由第一棵树的根节点指向
叶子结点u,再指向第二颗树的叶子结点，到根。root1-->u-->v-->root2，假设合并前u的深度为x，v的深度为y，则合并后支路的长度为L=x+y-1;
若L为奇数，则我们可以选择两种颜色，分别染1,2,1,...2,1。
若L为偶数，则我们可以选择两种颜色，分别染1,2,1,...2。
也就是说，这个图，我们从root1-->root2染色，如果只用1,2染色，那么所有支路的长度必须同为奇或同为偶。而这个奇偶又是由合并前叶子的深度决定的，所以先DFS
算深度，然后再if-else匹配。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define sys system("pause")
const int maxn=1e5+;
const int N=2e5+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p%mod;p=p*p%mod;q>>=;}return f;}
int n,m,k,tot=;
int cnt[N],dep1[N],dep2[N];
int a[N];
int d[][]={,,,,-,,,-};
vector<int>edg1[N],edg2[N],v1,v2;
queue<int>odd1,even1,odd2,even2;
void dfs1(int u,int fa){
dep1[u]=dep1[fa]+;
if(edg1[u].size()==){
if(dep1[u]&)odd1.push(u);
else even1.push(u);
return;
}
for(int i=;i<edg1[u].size();i++){
int v=edg1[u][i];
if(v!=fa)dfs1(v,u);
}
}
void dfs2(int u,int fa){
dep2[u]=dep2[fa]+;
if(edg2[u].size()==){
if(dep2[u]&)odd2.push(u);
else even2.push(u);
return;
}
for(int i=;i<edg2[u].size();i++){
int v=edg2[u][i];
if(v!=fa)dfs2(v,u);
}
}
int main()
{
int x,y,ans=,sum=;
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&x,&y);
edg1[x].pb(y);
edg1[y].pb(x);
}
for(int i=;i<=n;i++){
if(edg1[i].size()>){
dfs1(i,);
break;
}
}
scanf("%d",&m);
for(int i=;i<m;i++){
scanf("%d%d",&x,&y);
edg2[x].pb(y);
edg2[y].pb(x);
}
for(int i=;i<=m;i++){
if(edg2[i].size()>){
dfs2(i,);
break;
}
}
if(odd1.size()!=odd2.size()&&odd1.size()!=even2.size()){
puts("");
for(int i=;i<=n;i++){
if(edg1[i].size()==)v1.push_back(i);
}
for(int i=;i<=m;i++){
if(edg2[i].size()==)v2.push_back(i);
}
for(int i=;i<v1.size();i++){
printf("%d %d\n",v1[i],v2[i]);
}
}
else if(odd1.size()==even2.size()){
puts("");
while(!odd1.empty()){
int od1=odd1.front();odd1.pop();
int ev2=even2.front();even2.pop();
printf("%d %d\n",od1,ev2);
}
while(!even1.empty()){
int od2=odd2.front();odd2.pop();
int ev1=even1.front();even1.pop();
printf("%d %d\n",ev1,od2);
}
}
else if(odd1.size()==odd2.size()){
puts("");
while(!odd1.empty()){
int od1=odd1.front();odd1.pop();
int od2=odd2.front();odd2.pop();
printf("%d %d\n",od1,od2);
}
while(!even1.empty()){
int ev1=even1.front();even1.pop();
int ev2=even2.front();even2.pop();
printf("%d %d\n",ev1,ev2);
}
}
return ;