论#73毒瘤

#include <bits/stdc++.h>
using namespace std;
struct Tree
{
    int n;
    vector<int> head, to, nxt;
    int ec;
    Tree(int n_, int m) : n(n_), head(n_ + 1, -1), to(2 * m), nxt(2 * m), ec(0) {}
    inline void addEdge(int u, int v)
    {
        to[ec] = v;
        nxt[ec] = head[u];
        head[u] = ec++;
    }
};
static inline int bfs_farthest(const Tree &tr, int src, vector<int> &dist, vector<int> &par)
{
    dist.assign(tr.n + 1, -1);
    par.assign(tr.n + 1, -1);
    queue<int> q;
    q.push(src);
    dist[src] = 0;
    par[src] = -1;
    int far = src;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if (dist[u] > dist[far]) far = u;
        for (int e = tr.head[u]; e != -1; e = tr.nxt[e])
        {
            int v = tr.to[e];
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            par[v] = u;
            q.push(v);
        }
    }
    return far;
}
struct RootedInfo
{
    int n;
    int root;
    int K;
    vector<int> parent;
    vector<int> depth;
    vector<int> order;
    vector<int> cnt;
    vector<int> rep;
};
static inline RootedInfo build_rooted_component(const Tree &tr, int root, int bannedParent, int K)
{
    RootedInfo info;
    info.n = tr.n;
    info.root = root;
    info.K = K;
    info.parent.assign(tr.n + 1, -1);
    info.depth.assign(tr.n + 1, -1);
    info.cnt.assign(tr.n + 1, 0);
    info.rep.assign(tr.n + 1, -1);
    info.order.clear();
    info.order.reserve(tr.n);
    vector<int> st;
    st.reserve(tr.n);
    st.push_back(root);
    info.parent[root] = bannedParent;
    info.depth[root] = 0;
    while (!st.empty())
    {
        int u = st.back();
        st.pop_back();
        info.order.push_back(u);
        for (int e = tr.head[u]; e != -1; e = tr.nxt[e])
        {
            int v = tr.to[e];
            if (v == info.parent[u]) continue;
            if (info.depth[v] != -1) continue;
            info.parent[v] = u;
            info.depth[v] = info.depth[u] + 1;
            st.push_back(v);
        }
    }
    for (int idx = (int)info.order.size() - 1; idx >= 0; --idx)
    {
        int u = info.order[idx];
        if (info.depth[u] == K)
        {
            info.cnt[u] = 1;
            info.rep[u] = u;
        }
        for (int e = tr.head[u]; e != -1; e = tr.nxt[e])
        {
            int v = tr.to[e];
            if (v == info.parent[u]) continue;
            info.cnt[u] += info.cnt[v];
            if (info.rep[u] == -1 && info.rep[v] != -1) info.rep[u] = info.rep[v];
        }
    }
    return info;
}
struct TwoPick
{
    int a;
    int b;
    int lcaDepth;
};
static inline TwoPick pick_two_best(const Tree &tr, const RootedInfo &info, int start)
{
    if (info.cnt[start] <= 0)
        return TwoPick{info.root, info.root, info.K};
    if (info.cnt[start] == 1)
    {
        int x = info.rep[start];
        return TwoPick{x, x, info.K};
    }
    int x = start;
    while (true)
    {
        int c1 = -1, c2 = -1;
        for (int e = tr.head[x]; e != -1; e = tr.nxt[e])
        {
            int v = tr.to[e];
            if (v == info.parent[x]) continue;
            if (info.cnt[v] <= 0) continue;
            if (c1 == -1) c1 = v;
            else
            {
                c2 = v;
                break;
            }
        }
        if (c2 != -1)
        {
            return TwoPick{info.rep[c1], info.rep[c2], info.depth[x]};
        }
        for (int e = tr.head[x]; e != -1; e = tr.nxt[e])
        {
            int v = tr.to[e];
            if (v == info.parent[x]) continue;
            if (info.cnt[v] > 0)
            {
                x = v;
                break;
            }
        }
    }
}
static inline vector<int> path_to_ancestor(int u, int anc, const vector<int> &parent)
{
    vector<int> res;
    while (u != -1)
    {
        res.push_back(u);
        if (u == anc) break;
        u = parent[u];
    }
    return res;
}
static inline vector<int> build_path_via_center(int a, int b, int center, const vector<int> &parent)
{
    vector<int> left = path_to_ancestor(a, center, parent);
    vector<int> right = path_to_ancestor(b, center, parent);
    reverse(right.begin(), right.end()); 
    for (int i = 1; i < (int)right.size(); ++i) left.push_back(right[i]);
    return left;
}
static inline vector<int> build_path_via_edge(int a, int u, int v, int b,
        const vector<int> &parU, const vector<int> &parV)
{
    vector<int> left = path_to_ancestor(a, u, parU); 
    vector<int> right = path_to_ancestor(b, v, parV); 
    reverse(right.begin(), right.end()); 
    vector<int> res;
    res.reserve(left.size() + 1 + right.size());
    for (int x : left) res.push_back(x);
    res.push_back(v);
    for (int i = 1; i < (int)right.size(); ++i) res.push_back(right[i]);
    return res;
}
static inline void print_path(const vector<int> &p)
{
    for (int i = 0; i < (int)p.size(); ++i)
    {
        cout << p[i] << (i + 1 == (int)p.size() ? '\n' : ' ');
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    Tree tr(n, n - 1);
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;
        tr.addEdge(x, y);
        tr.addEdge(y, x);
    }
    vector<int> dist, par;
    int s = bfs_farthest(tr, 1, dist, par);
    int t = bfs_farthest(tr, s, dist, par);
    vector<int> P;
    for (int x = t; x != -1; x = par[x]) P.push_back(x);
    reverse(P.begin(), P.end());
    int D = (int)P.size() - 1;
    int L = D + 1;
    vector<int> pathA, pathB;
    if (D % 2 == 0)
    {
        int c = P[D / 2];
        int r = D / 2;
        RootedInfo info = build_rooted_component(tr, c, -1, r);
        vector<int> subs;
        subs.reserve(8);
        for (int e = tr.head[c]; e != -1; e = tr.nxt[e])
        {
            int v = tr.to[e];
            if (info.cnt[v] > 0) subs.push_back(v);
        }
		if ((int)subs.size() >= 4)
        {
            int a1 = info.rep[subs[0]];
            int a2 = info.rep[subs[1]];
            int b1 = info.rep[subs[2]];
            int b2 = info.rep[subs[3]];
            pathA = build_path_via_center(a1, a2, c, info.parent);
            pathB = build_path_via_center(b1, b2, c, info.parent);
        }
        else if ((int)subs.size() == 3)
        {
			int R = subs[0];
            TwoPick bestR = pick_two_best(tr, info, R);
            for (int i = 1; i < 3; ++i)
            {
                TwoPick cand = pick_two_best(tr, info, subs[i]);
                if (cand.lcaDepth < bestR.lcaDepth)
                {
                    bestR = cand;
                    R = subs[i];
                }
            }
            int X = -1, Y = -1;
            for (int u : subs)
            {
                if (u == R) continue;
                if (X == -1) X = u;
                else Y = u;
            }
            int endX = info.rep[X];
            int endY = info.rep[Y];
            pathA = build_path_via_center(bestR.a, endX, c, info.parent);
            pathB = build_path_via_center(bestR.b, endY, c, info.parent);
        }
        else
        {
            int A = subs[0], B = subs[1];
            TwoPick pA = pick_two_best(tr, info, A);
            TwoPick pB = pick_two_best(tr, info, B);
            pathA = build_path_via_center(pA.a, pB.a, c, info.parent);
            pathB = build_path_via_center(pA.b, pB.b, c, info.parent);
        }
    }
    else
    {
        int u = P[D / 2];
        int v = P[D / 2 + 1];
        int k = D / 2;
        RootedInfo infoU = build_rooted_component(tr, u, v, k); // u-side, block v
        RootedInfo infoV = build_rooted_component(tr, v, u, k); // v-side, block u
        TwoPick pU = pick_two_best(tr, infoU, u);
        TwoPick pV = pick_two_best(tr, infoV, v);
        pathA = build_path_via_edge(pU.a, u, v, pV.a, infoU.parent, infoV.parent);
        pathB = build_path_via_edge(pU.b, u, v, pV.b, infoU.parent, infoV.parent);
    }
	if ((int)pathA.size() != L) pathA = P;
    if ((int)pathB.size() != L) pathB = P;
    cout << L << "\n";
    print_path(pathA);
    print_path(pathB);
    return 0;
}