牛客多校2-Cover the tree

题意：

　　给定一棵无根树，求用最少的链覆盖树上所有的边，并输出每条链的首位两端编号

做法：

　　首先确认需要多少条链来覆盖所有边。

　　显然，当n = 1时，只需要一条，链头尾编号都为1

　　　　　当n = 2时，需要一条，链头尾为1， 2

　　　　　当n >= 3时，上述两种情况链的头尾都是入度为1的点，而确实，当从一个叶子节点1出发，向上走到假定的根节点，再往下走到叶子节点2，如此反复形成的链，足以覆盖所有的边，并确为最少情况。

　　　　　但此法仅于叶子节点为偶数时适用，如何在叶子节点个数为奇数时确定最少链数，只需让根节点和最后剩余的叶子节点成链即可。

　　　　　对于每个叶子节点分配一个dfs序，用dfn[]数组记录，找到一个非叶子节点作为根节点，把一个树分成假定的左右子树，让每条链的两端分别处于左右不同的子树即可。

遍历一棵树的时间复杂度O(n)

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29 
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47 
 48 const int maxn = 2e5 + 7;
 49 
 50 vector<int> g[maxn];
 51 int n;
 52 
 53 int du[maxn];
 54 int dfn[maxn];
 55 int vis[maxn];
 56 int cnt = 0;
 57 
 58 void dfs(int u, int fa) {
 59     int d = g[u].size();
 60     for ( int i = 0; i < d; ++i ) {
 61         int v = g[u][i];
 62         if(v == fa || vis[v]) {
 63             continue;
 64         }
 65         vis[v] = 1;
 66         dfs(v, u);
 67     }
 68     if(d == 1) {
 69         dfn[++cnt] = u;
 70     }
 71 }
 72 
 73 int main()
 74 {
 75     read(n);
 76     for ( int i = 1; i <= n - 1; ++i ) {
 77         int u, v;
 78         read(u); read(v);
 79         g[u].push_back(v);
 80         g[v].push_back(u);
 81         ++du[u], ++du[v];
 82     }
 83     int root = -1;
 84     int num = 0;
 85     for ( int i = 1; i <= n; ++i ) {
 86         if(du[i] == 1) {
 87             ++num;
 88         }
 89     }
 90     for ( int i = 1; i <= n; ++i ) {
 91         if(du[i] > 1) {
 92             root = i;
 93             break;
 94         }
 95     }
 96     int ans = num / 2;
 97     if(num & 1) {
 98         ++ans;
 99     }
100     if(n == 1) {
101         cout << "1 1" << endl;
102         return 0;
103     }
104     if(n == 2) {
105         cout << "1 2" << endl;
106         return 0;
107     }
108     dfs(root, -1);
109     // for ( int i = 1; i <= cnt; ++i ) {
110     //     printf("dfn[%d]:%d
",i, dfn[i]);
111     // }
112     int mid = (cnt + 1) >> 1;
113     // dbg(mid);
114     cout << ans << endl;
115     for ( int i = 1; i <= cnt - mid; ++i ) {
116         printf("%d %d
",dfn[i], dfn[i + mid]);
117     }
118     if(cnt & 1) {
119         printf("%d %d
",dfn[mid], root);
120     }
121     return 0;
122 }