题解：AT_arc156_c [ARC156C] Tree and LCS

· · 题解

真心感觉质量很好。

观察：数据为什么只有 5000？checker 的复杂度比较高对不对。观察样例+打表可以得到答案不会很大，应该是 1。

分析下界，对于任意排列中 P_i，每次选路径 (i,P_i) 至少有 1 的贡献，考虑构造。

可以先手玩一下一条 1\to n 的链，显然排列直接 n\to 1 就好了。要是只有链这个条件呢？每次选出两端的点 x,y，直接 P_x=y,P_y=x，就是对的，因为这样选，无论怎么找路径，始终是交错的，选了这个就选不了那个，合法了。拓展到正常的树，引用上面的想法，我们每次选出两个叶子，像上面一样操作，就可以合法了。有一个归纳证明：n\le 2 显然合法；考虑 n>3，删掉两个点会变成 n-2 规模的问题，注意到我们这样构造，删掉叶子因为是交错的，不会对答案造成更多影响，或者反证：因为 n-2 规模答案为 1，那么选删掉的两个点为路径端点的路径一定不劣，只有新的点才有贡献，但是实际上产生不了贡献，所以是对的。

代码如下

#include<bits/stdc++.h>
using namespace std;

const int N = 5e3 + 7;

int n, deg[N], ans[N];
vector<int> G[N];

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        ++deg[u], ++deg[v]; 
    }
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(deg[i] == 1) q.push(i);
    while((int)q.size() >= 2)
    {
        int x[2];
        x[0] = q.front(); q.pop();
        x[1] = q.front(); q.pop();
        ans[x[1]] = x[0], ans[x[0]] = x[1];
        for(int i = 0; i < 2; i++)
        {
            for(int v : G[x[i]])
            {
                if(ans[v]) continue ;
                if(--deg[v] == 1) q.push(v);
            }
        }
    }
    if(!q.empty())
    {
        int x = q.front(); q.pop();
        ans[x] = x;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    return 0;
}