首页 > 代码库 > POJ/obc - Step Traversing a Tree

POJ/obc - Step Traversing a Tree

即黑书里的“隔三遍历”,具体分析见黑书,我只是想了下证明没啥好说的。

#include <cstdio>

#define MAXV    5005
#define MAXE    ((MAXV << 1) - 2)

int N;
int Vefw[MAXE], Vt[MAXE], Veh[MAXV], Veptr;
int V_b8[MAXV];

int leafrch(int s)
{
    int ret = s;
    V_b8[s] = 1;
    for(int e = Veh[s]; e; e = Vefw[e]) {
        int t = Vt[--e];
        if (!V_b8[t]) {
                ret = leafrch(t);
                break;
        }
    }
    V_b8[s] = 0;
    return ret;
}

void solve(int c, int s)
{
    V_b8[s] = 1;
    if (c & 1) printf("%d\n", s+1);
    for(int e=Veh[s]; e; e = Vefw[e]) {
        int t = Vt[--e];
        if (!V_b8[t])
            solve(c+1, t);
    }
    if (!(c & 1)) printf("%d\n", s+1);
    V_b8[s] = 0;
}

#define addedge(j,k) ({\
    Vefw[Veptr] = Veh[j], Vt[Veptr] = k;        Veh[j] = ++Veptr;    })

int main(void)
{

    scanf("%d", &N);
    int fakeroot = 0;
    for(int i=0; i<N-1; ++i) {
        int j, k;
        scanf("%d%d", &j, &k); --j, --k;
        addedge(j, k), addedge(k, j);
        if (k == fakeroot) fakeroot = j;
    }
    solve(1, leafrch(fakeroot));
    return 0;
}

测试结果:

Test case Status Time/Limit Points
 0   OK 0.00s/0.10s 0/0
 1   OK 0.00s/0.10s 9/9
 2   OK 0.00s/0.10s 9/9
 3   OK 0.00s/0.10s 9/9
 4   OK 0.00s/0.10s 9/9
 5   OK 0.01s/0.10s 9/9
 6   OK 0.01s/0.10s 9/9
 7   OK 0.00s/0.10s 9/9
 8   OK 0.00s/0.10s 9/9
 9   OK 0.01s/0.10s 9/9
 10   OK 0.01s/0.10s 9/9
 11   OK 0.01s/0.10s 10/10