URAL/1389

来自"NOCOW"

啊啊啊，输出方案的树型DP什麽的，最讨厌了。

#include <cstdio>
#include <cstdlib>
#define F(x,y) ((x<<1)|(y))
#define G(x,y) ((y)?(x>>1):(x&1))
const int maxn=100010,maxm=(maxn<<1);
int n,m,a,b,tot=0,ans=0,f[maxn][2]={0},p[maxn][2]={0};
int h[maxn]={0},node[maxm],next[maxm];
bool v[maxn]={false};
void addedge(int a,int b)
{
    node[++tot]=b;
    next[tot]=h[a];
    h[a]=tot;
}
void dfs(int x,int fa)
{
    for (int i=h[x];i;i=next[i])
        if (node[i] != fa)
        {
            dfs(node[i],x);
            f[x][0]+=f[node[i]][1];
        }
    for (int i=h[x];i;i=next[i])
        if (node[i] != fa)
            if (f[x][0]-f[node[i]][1]+f[node[i]][0]+1 > f[x][1])
            {
                f[x][1]=f[x][0]-f[node[i]][1]+f[node[i]][0]+1;
                p[x][1]=F(node[i],0);
            }
}
void print(int s,int fa)
{
    if (!G(s,1))  return;
    int t=G(p[G(s,1)][G(s,0)],1);
    for (int i=h[G(s,1)];i;i=next[i])
        if ((node[i] != t) && (node[i] != fa))
            print(F(node[i],1),G(s,1));
    if (t)
    {
        printf("%d %d\n",t,G(s,1));
        print(p[G(s,1)][G(s,0)],G(s,1));
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    dfs(1,0);
    printf("%d\n",f[1][1]);
    print(F(1,1),F(0,0));
    return 0;
}
//by zzy