链接：https://ac.nowcoder.com/acm/contest/5667/C
来源：牛客网
题意
给你一棵树 让你找出最小数量的“链”（链就是树上任意两点连线）使得覆盖所有边。
思路
dfs序 从左到右存遍历到的叶子节点
然后 从第一个和中间开始遍历 若最后剩下一个 和之前的任意一个叶子相连即可
如十个叶子节点
左指针刚开始在1 右指针刚开始在6 然后配对完。
代码
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define inf 0x3f3f3f3f
#define sd(a) scanf("%d",&a)
#define sdd(a,b) scanf("%d%d",&a,&b)
#define cl(a,b) memset(a,b,sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define dbg() printf("aaa\n")
using namespace std;
const int maxn=2e5+10;
int n,cnt;
struct Side{int v,next;
}side[maxn<<1];
int head[maxn];
int deg[maxn];//度数
bool con[maxn];//有没有访问过这个点
int p;
int no[maxn];//记录顺序
void add(int u,int v){side[cnt].v=v;side[cnt].next=head[u];head[u]=cnt;cnt++;
}
void dfs(int u,int pre){if(deg[u]==1){p++;no[p]=u;}for(int i=head[u];i!=-1;i=side[i].next){int v=side[i].v;if(v==pre) continue;dfs(v,u);}
}
int main() {sd(n);cl(head,-1);rep(i,1,n-1){int u,v;sdd(u,v);add(u,v);add(v,u);deg[u]++;deg[v]++;}if(n==1){printf("0\n");return 0;}else if(n==2){printf("1\n1 2\n");return 0;}//至少仨点p=0;rep(i,1,n){if(deg[i]>1){//不是叶子结点dfs(i,-1);break;}}printf("%d\n",p/2+p%2);int i=1,j=p/2+1;while(i<=p/2){printf("%d %d\n",no[i],no[j]);i++;j++;}if(p&1){//若还单着一个printf("%d %d\n",no[1],no[p]);}return 0;
}
题目描述
Given an unrooted tree, you should choose the minimum number of chains that all edges in the tree are covered by at least one chain. Print the minimum number and one solution. If there are multiple solutions, print any of them.
输入描述:
The first line contains one integer n~(1\leq n \leq 2\times10^5)n (1≤n≤2×10
5
), denoting the size of the tree.
Following {n-1}n?1 lines each contains two integers u,v~(1\leq u < v \leq n)u,v (1≤u<v≤n), denoting an edge in the tree.
It’s guaranteed that the given graph forms a tree.
输出描述:
The first line contains one integer {k}k, denoting the minimum number of chains to cover all edges.
Following {k}k lines each contains two integers u,v~(1\leq u,v \leq n)u,v (1≤u,v≤n), denoting a chain you have chosen. Here {u = v}u=v is permitted, which covers no edge.
示例1
输入
复制
5
1 2
1 3
2 4
2 5
输出
复制
2
2 3
4 5
说明