\u3002\u3002\u6811\u7684\u8def\u5f84\u8986\u76d6\u3002<\/p>\n
<\/p>\n
\r\nconst int N = 10009;\r\n\r\nint hd[N], suc[N*2], to[N*2], deg[N]; VI adj[N];\r\nint f0[N], f1[N], p0[N], p1[N]; bool vis[N];\r\nint n;\r\n\r\n#define v to[i]\r\nvoid dfs(int p = 0, int u = 1){\r\n\r\n REP_G(i, u) if (v != p){\r\n dfs(u, v), f0[u] += f0[v];\r\n }\r\n\r\n if (!f0[u]){ \/\/ is leaf .. .\r\n f0[u] = f1[u] = 1;\r\n }\r\n else {\r\n f1[u] = f0[u];\r\n\r\n int t1 = INF; REP_G(i, u) if (v != p){\r\n if (f1[v] - f1[v] < t1){\r\n t1 = f1[v] - f0[v];\r\n p1[u] = v;\r\n }\r\n }\r\n\r\n int t0 = INF; REP_G(i, u) if (v != p && v != p1[u]){\r\n if (f1[v] - f1[v] < t0){\r\n t0 = f1[v] - f0[v];\r\n p0[u] = v;\r\n }\r\n }\r\n f1[u] += t1, f0[u] += t0 + t1 - 1;\r\n checkMin(f0[u], f1[u]);\r\n }\r\n}\r\n\r\nvoid gao(int u = 1, bool flag = false){ \/\/ \u662f\u5426\u5141\u8bb8\u5206\u5c94\u3002\r\n\r\n vis[u] = true;\r\n\r\n if (p0[u] && !flag){\r\n adj[u].PB(p0[u]);\r\n adj[p0[u]].PB(u);\r\n gao(p0[u], 1);\r\n }\r\n\r\n if (p1[u]){\r\n adj[u].PB(p1[u]);\r\n adj[p1[u]].PB(u);\r\n gao(p1[u], 1);\r\n }\r\n\r\n REP_G(i, u) if (!vis[v]) gao(v) ;\r\n}\r\n\r\n\r\n#undef v\r\n#define v (*it)\r\nvoid out(int u){\r\n vis[u] = true; ECH(it, adj[u]) if (!vis[v]){\r\n printf(" %d" , v);\r\n out(v) ;\r\n }\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n#define a to[i^1]\r\n#define b to[i]\r\n\r\n Rush{\r\n\r\n RST(hd, f0, f1, p0, p1);\r\n\r\n FOR_C(i, 2, RD(n)<<1){\r\n RD(a, b);\r\n suc[i] = hd[a], hd[a] = i++;\r\n suc[i] = hd[a], hd[a] = i;\r\n }\r\n\r\n dfs(); OT(f0[1]);\r\n\r\n REP_1(i, n) CLR(adj[i]);\r\n\r\n RST(vis); gao(); RST(vis); REP_1(u, n) if (!vis[u] && SZ(adj[u]) <= 1){\r\n printf("%d", u); out(u);\r\n puts("");\r\n }\r\n }\r\n}\r\n<\/pre>\n\r\nconst int N = 10009;\r\n\r\nint hd[N], suc[N*2], to[N*2], deg[N];\r\nbool vis[N];\r\nint n;\r\n\r\n#define v to[i]\r\n\r\nVVI path; VI cur;\r\n\r\nvoid gao(int u){\r\n vis[u] = true; cur.PB(u);\r\n REP_G(i, u) if (!vis[v]) gao(v);\r\n}\r\n\r\nvoid dfs(int p = 0, int u = 1){\r\n\r\n \/\/cout << " " << u << endl;\r\n\r\n REP_G(i, u) if (v != p){\r\n dfs(u, v);\r\n }\r\n\r\n \/\/cout << u << " " << deg[u] << endl;\r\n\r\n if (deg[u] <= 1 && p) ++deg[p];\r\n else {\r\n int c = 0; CLR(cur); vis[u] = true;\r\n REP_G(i, u) if (v != p && deg[v] <= 1){\r\n\r\n \/*cout << "--" << u << " " << v << endl;\r\n cout << "--"; REP(i, SZ(cur)) cout << cur[i] << " ";\r\n cout << endl;*\/\r\n\r\n if (!c) gao(v), reverse(ALL(cur)), cur.PB(u);\r\n else if (c == 1) gao(v);\r\n else{\r\n if (SZ(cur)) path.PB(cur), CLR(cur);\r\n gao(v);\r\n }\r\n ++c;\r\n }\r\n \/\/cout << c << endl;\r\n\r\n if (SZ(cur)) path.PB(cur);\r\n else if (!c) cur.PB(u), path.PB(cur);\r\n }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n#define a to[i^1]\r\n#define b to[i]\r\n\r\n Rush{\r\n\r\n RST(hd, deg, vis); CLR(path);\r\n\r\n FOR_C(i, 2, RD(n)<<1){\r\n RD(a, b);\r\n suc[i] = hd[a], hd[a] = i++;\r\n suc[i] = hd[a], hd[a] = i;\r\n }\r\n\r\n dfs();\r\n\r\n OT(SZ(path)); REP(i, SZ(path)){\r\n printf("%d", path[i][0]); FOR(j, 1, SZ(path[i])) printf(" %d", path[i][j]);\r\n puts("");\r\n }\r\n }\r\n}\r\n<\/pre>\n\uff08\u65e0\u8bba\u4ece\u54ea\u65b9\u9762\u770b\u3002\u3002\u8fd9\u9898\u4f3c\u4e4e\u3002\u3002\u8d2a\u5fc3\u90fd\u8981\u66f4\u4f18\u8d8a\u4e00\u4e9b\u3002\u3002\/w\\\u3002\u3002<\/p>\n
External link: <\/h3>\n