代码

// 2002 【NOIP2018】旅行（加强版） — O(n+m) with online cut decision.
//
// For a base-ring tree the optimal travel = greedy sorted DFS of T minus one
// cycle edge.  While walking the cycle in the first-chosen direction, at the
// moment the DFS wants to step onto the forward cycle edge (u->v), cutting that
// edge yields next node M = the deepest pending child on the DFS stack, while
// continuing yields v.  All candidates that continue share v at that position,
// so cut iff M < v (labels are distinct).  That decision is final.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

typedef unsigned long long u64;

#ifdef TEST_IO
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM = 1u << 28;
#else
struct DI { u64 abi; const char*in; u64 insz; char*out; u64 outlim; u64 outsz; char*err;
            u64 errlim; u64 errsz; const char*IB; u64 IBlim; char*OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));
#define DUCKINFO 0x243FFF90ULL
static struct DI *di;
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM;
#endif

static const int MAXN = 500005;
static int n, m;
static int eu[MAXN], ev[MAXN];
static int start_[MAXN + 1], adj[2 * MAXN];
static int deg[MAXN];
static int seq_[MAXN];
static int visited[MAXN], visStamp = 1;
static int isCyc[MAXN];
static int fbn[MAXN];
static int stkNode[MAXN], stkPtr[MAXN], nxtPtr[MAXN], deepBelow[MAXN];

static inline void buildGraph() {
    for (int i = 1; i <= n; i++) deg[i] = 0;
    for (int i = 0; i < m; i++) { deg[eu[i]]++; deg[ev[i]]++; }
    int s = 0;
    for (int i = 1; i <= n; i++) { start_[i] = s; s += deg[i]; }
    start_[n + 1] = s;
    static int pos[MAXN];
    for (int i = 1; i <= n; i++) pos[i] = start_[i];
    for (int i = 0; i < m; i++) {
        adj[pos[eu[i]]++] = ev[i];
        adj[pos[ev[i]]++] = eu[i];
    }
    for (int i = 1; i <= n; i++) {
        int d = start_[i + 1] - start_[i];
        if (d <= 1) continue;
        if (d <= 24) {
            for (int a = start_[i] + 1; a < start_[i + 1]; a++) {
                int x = adj[a], b = a - 1;
                while (b >= start_[i] && adj[b] > x) { adj[b + 1] = adj[b]; b--; }
                adj[b + 1] = x;
            }
        } else std::sort(adj + start_[i], adj + start_[i + 1]);
    }
}

static inline int nextUnv(int lvl) {
    int u = stkNode[lvl];
    int i = nxtPtr[lvl], e = start_[u + 1], fb = fbn[u];
    while (i < e) { int w = adj[i]; if (visited[w] != visStamp && w != fb) break; i++; }
    nxtPtr[lvl] = i;
    return i < e ? i : -1;
}

int main() {
#ifdef TEST_IO
    static char inbuf[1 << 26];
    INSZ = fread(inbuf, 1, sizeof(inbuf), stdin);
    IN = inbuf;
    static char outbuf[1 << 25];
    OUT = outbuf; OUTLIM = sizeof(outbuf);
#else
    di = (struct DI *)DUCKINFO;
    IN = di->in; INSZ = di->insz;
    OUT = di->out; OUTLIM = di->outlim;
#endif
    const char *p = IN, *pend = IN + INSZ;
    auto readInt = [&]() -> int {
        while (p < pend && (*p < '0' || *p > '9')) p++;
        int v = 0;
        while (p < pend && *p >= '0' && *p <= '9') v = v * 10 + (*p++ - '0');
        return v;
    };
    n = readInt(); m = readInt();
    for (int i = 0; i < m; i++) { eu[i] = readInt(); ev[i] = readInt(); }
    buildGraph();
    memset(fbn, -1, sizeof(int) * (n + 2));
    memset(isCyc, 0, sizeof(int) * (n + 2));

    if (m == n) {
        static int d2[MAXN], queue_[MAXN];
        for (int i = 1; i <= n; i++) d2[i] = start_[i + 1] - start_[i];
        int qh = 0, qt = 0;
        for (int i = 1; i <= n; i++) if (d2[i] == 1) queue_[qt++] = i;
        while (qh < qt) {
            int u = queue_[qh++];
            for (int i = start_[u]; i < start_[u + 1]; i++) {
                int v = adj[i];
                if (d2[v] > 1) { if (--d2[v] == 1) queue_[qt++] = v; }
            }
            d2[u] = 0;
        }
        for (int i = 1; i <= n; i++) if (d2[i] > 1) isCyc[i] = 1;
    }

    // greedy DFS with online cut decision
    int len = 0, sp = 0, cutMade = 0;
    ++visStamp;
    visited[1] = visStamp; seq_[len++] = 1;
    stkNode[0] = 1; stkPtr[0] = start_[1]; nxtPtr[0] = start_[1]; deepBelow[0] = -1;
    while (sp >= 0) {
        int u = stkNode[sp];
        int i = nextUnv(sp);
        if (i < 0) { sp--; continue; }
        int v = adj[i];
        if (!cutMade && isCyc[u] && isCyc[v]) {
            int save = nxtPtr[sp];
            nxtPtr[sp] = i + 1;
            int j = nextUnv(sp);
            nxtPtr[sp] = save;
            if (j < 0) {
                int d = deepBelow[sp];
                if (d >= 0) {
                    int mi = nextUnv(d);
                    if (mi >= 0 && adj[mi] < v) {
                        fbn[u] = v; fbn[v] = u; cutMade = 1;
                        continue;
                    }
                }
            }
        }
        stkPtr[sp] = i + 1; nxtPtr[sp] = i + 1;
        visited[v] = visStamp; seq_[len++] = v;
        sp++;
        stkNode[sp] = v; stkPtr[sp] = start_[v]; nxtPtr[sp] = start_[v];
        int pr = nextUnv(sp - 1);
        deepBelow[sp] = (pr >= 0) ? sp - 1 : deepBelow[sp - 1];
    }

    char *o = OUT;
    for (int i = 0; i < len; i++) {
        int v = seq_[i];
        char tmp[12];
        int k = 0;
        do { tmp[k++] = (char)('0' + v % 10); v /= 10; } while (v);
        while (k) *o++ = tmp[--k];
        *o++ = (i + 1 == len) ? '\n' : ' ';
    }
    OUTSZ = (u64)(o - OUT);
#ifdef TEST_IO
    fwrite(outbuf, 1, OUTSZ, stdout);
#else
    di->outsz = OUTSZ;
    register long rax __asm__("rax") = 60;
    register long rdi __asm__("rdi") = 0;
    __asm__ volatile("syscall" :: "a"(rax), "D"(rdi) : "rcx", "r11", "memory");
    __builtin_unreachable();
#endif
    return 0;
}

评测结果