题目大意：$NOIP\;TG\;D2T1$
题解：一棵树的很简单，第一个点一定是$1$，只需要对每个节点，找最小的没有访问过的节点访问即可，我写的是$O(n\log_2n)$。
考虑基环树的部分，一个显然的想法是枚举一条环上的边，然后删掉，跑树的部分，复杂度为$O(mn\log_2n)$，明显过不了。于是考场上的我开始发扬人类智慧，发现有一个环上的边可以不经过，可以找这一条边的贡献，若不经过这条边的下一位和经过这条边的下一位进行比较，若不经过较优则不经过这条边。
出来问了一下，发现可以先把每个点的子树的儿子排序，再枚举删除的边可以做到$O(nm)$，可以过。
卡点：考试时写的代码可能会“多删除”几条边导致出错，并且仅当环上的点为当前的节点儿子中最大的节点时才会断这条边，而考场上没考虑到。考场上写了一个环的部分分，没有考虑到走回去的情况（如果不写，我的那个假的程序是可以跑对的，也就是说我白白丢了$12$分还花了时间，自闭了）
C++ Code：
#include#include #include #define maxn 5010inline int min(int a, int b) {return a < b ? a : b;}int head[maxn], cnt = 1;struct Edge { int to, nxt; bool can;} e[maxn << 1];inline void add(int a, int b) { e[++cnt] = (Edge) {b, head[a], true}; head[a] = cnt;}int n, m;namespace Work1 { int ans[maxn], idx; void dfs(int u, int fa = 0) { ans[++idx] = u; std::vector V; V.clear(); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa) V.push_back(v); } std::sort(V.begin(), V.end()); for (std::vector ::iterator it = V.begin(); it != V.end(); it++) { dfs(*it, u); } } int main() { for (int i = 1, a, b; i < n; i++) { scanf("%d%d", &a, &b); add(a, b); add(b, a); } dfs(1); for (int i = 1; i <= n; i++) { printf("%d", ans[i]); putchar(i == n ? '\n' : ' '); } return 0; }}namespace Work2 { int C; int ans[maxn], p[maxn], idx; bool vis[maxn]; int res[maxn], scc; int in_C = 0; bool used_C = false; void dfs(int u, int fa = 0, int last = n + 1) { vis[u] = true; ans[++idx] = u; std::vector V; V.clear(); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v] && v != fa) V.push_back(v); } std::sort(V.begin(), V.end()); for (std::vector ::iterator it = V.begin(); it != V.end(); it++) if (!vis[*it]) { if (res[u] == res[*it]) { if (in_C == u) used_C = true; if (!in_C) in_C = u; if (used_C) { dfs(*it, u, n + 1); } else { if ((it + 1) == V.end()) { if (*it < last) dfs(*it, u, last); else used_C = true; } else dfs(*it, u, *(it + 1)); } } else dfs(*it, u, n + 1); } } int DFN[maxn], low[maxn]; int S[maxn], top; void tarjan(int u, int father = 0) { DFN[u] = low[u] = ++idx; S[++top] = u; int v; for (int i = head[u]; i; i = e[i].nxt) if (i ^ father ^ 1) { v = e[i].to; if (!DFN[v]) { tarjan(v, i); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], DFN[v]); } if (DFN[u] == low[u]) { scc++; do { v = S[top--]; res[v] = scc; } while (v != u); } } inline bool check() { for (int i = 1; i <= n; i++) if (ans[i] != p[i]) { return p[i] < ans[i]; } return false; } void dfs2(int u, int fa = 0) { p[++idx] = u; std::vector V; V.clear(); for (int i = head[u]; i; i = e[i].nxt) if (e[i].can) { int v = e[i].to; if (v != fa) V.push_back(v); } std::sort(V.begin(), V.end()); for (std::vector ::iterator it = V.begin(); it != V.end(); it++) { dfs2(*it, u); } } int main() { for (int i = 0, a, b; i < n; i++) { scanf("%d%d", &a, &b); add(a, b); add(b, a); } tarjan(1); for (int i = 1; i <= n; i++) ans[i] = n; if (n < 500) { for (int i = 2; i <= cnt; i += 2) { int u = e[i ^ 1].to, v = e[i].to; if (res[u] == res[v]) { idx = 0; e[i].can = e[i ^ 1].can = false; dfs2(1); if (check()) { for (int j = 1; j <= n; j++) ans[j] = p[j]; } e[i].can = e[i ^ 1].can = true; } } for (int i = 1; i <= n; i++) { printf("%d", ans[i]); putchar(i == n ? '\n' : ' '); } return 0; } for (int i = 2; i <= cnt; i += 2) { int u = e[i ^ 1].to, v = e[i].to; if (res[u] == res[v]) { C = res[u]; break; } } idx = 0; dfs(1); for (int i = 1; i <= n; i++) { printf("%d", ans[i]); putchar(i == n ? '\n' : ' '); } return 0; }}int main() { scanf("%d%d", &n, &m); if (n - 1 == m) { return Work1::main(); } if (n == m) { return Work2::main(); } return 0;}