一、题目
这道题考试时候打了缩点，然后一无所获，虽然想出了那个超级神奇的构造方法。
还是不要思维定式啊，我以为难的图论题一定要缩点，但是我从来一打缩点就爆炸。
二、解法
比较传统的树上二选一构造问题，根据套路任何情况一定有解。
直接考虑 \(\tt dfs\) 树，叶子之间一定无边，如果有 \(\geq\lfloor\frac{n}{3}\rfloor\) 个叶子（不考虑根），那么我们找到解。
那么有叶子数量 \(<\lfloor\frac{n}{3}\rfloor\)，考虑根是叶子也只有至多 \(\lfloor\frac{n}{3}\rfloor\) 个点，那么我们把它们两两匹配得到路径至多有 \(\lceil\frac{n}{6}\rceil\) 条。
现在问题转化成了构造一个叶子的匹配，使得树上所有点都被覆盖。我的方法：把所有叶子按 \(\tt dfs\) 序排序，设一共有 \(k\) 个叶子（如果 \(k\) 是奇数那么我们补上根），然后 \(i\) 和 \(i+\frac{k}{2}\) 匹配。
已经过了，跪求上面叶子匹配构造方法的正确性证明。
#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 1005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,tot,Ind,cnt,f[M],dfn[M];
int fa[M],id[M],dep[M],a[M],b[M];
struct edge
{
int v,next;
}e[M*M];
void dfs(int u)
{
dfn[u]=++Ind;int sz=0;
dep[u]=dep[fa[u]]+1;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(dfn[v]) continue;
fa[v]=u;dfs(v);
sz++;
}
if(sz==0 || (sz==1 && u==1))
id[++k]=u;
}
int cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
void match(int u,int v)
{
int t1=0,t2=0;cnt++;
while(u!=v)
{
if(dep[u]>dep[v])
a[++t1]=u,u=fa[u];
else
b[++t2]=v,v=fa[v];
}
a[++t1]=u;
printf("%d ",t1+t2);
for(int i=1;i<=t1;i++)
printf("%d ",a[i]);
for(int i=t2;i>=1;i--)
printf("%d ",b[i]);
puts("");
}
signed main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
e[++tot]=edge{v,f[u]},f[u]=tot;
e[++tot]=edge{u,f[v]},f[v]=tot;
}
dfs(1);int fl=0;
if(id[k]==1) k--,fl=1;
if(k>=n/3)
{
puts("2");
for(int i=1;i<=n/3;i++)
printf("%d ",id[i]);
puts("");
return 0;
}
if(fl==1) id[++k]=1;
if(k%2) id[++k]=1;
sort(id+1,id+1+k,cmp);
puts("1");
for(int i=1;i<=k/2;i++)
match(id[i],id[i+k/2]);
for(int i=2;i<=n;i++)
if(cnt<(n+5)/6)
{
printf("%d %d\n",1,i);
cnt++;
}
}