AtCoder Regular Contest 156 C. Tree and LCS（思维题 构造 数学归纳法）

题目

构造一个排列p，

使得对于任意树上路径，

求该路径上的点(x1,...,xk)和对应排列上的点(Px1,...,Pxk)的最长公共子序列都得到一个值，

称为相似值

现在想令任意树上路径的相似值的最大可能长度最小，

最小化前提下，输出这个排列p

思路来源

官方题解

题解

其实就是想想，线性序列怎么拓展成树上序列

线性序列的话，1 2 3 4 5和5 4 3 2 1就可以了，也就是取逆序序列，此时最长公共子序列值为1

并且，去除掉两端的1和5之后，剩下的子段仍然满足要求

树上的话，考虑两个叶子u和v，令ans[u]=v，ans[v]=u，

只有同时包含(u,v)的路径里能同时有u值和v值，并且这俩是满足线性序列两端的条件的

可以同时去除掉，然后递归到n-2个点的情况，

所以就是类似拓扑排序，一开始把所有叶子塞进队列里，

每次剥掉两个叶子，把产生的新叶子再塞进队列里，

最后如果只剩一个点的话令其等于自身即可

代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=5e3+10;
int n,u,v,deg[N],ans[N];
vector<int>e[N];
queue<int>q;
int main(){
    sci(n);
    rep(i,2,n){
        sci(u),sci(v);
        deg[u]++;
        deg[v]++;
        e[u].pb(v);
        e[v].pb(u);
    }
    rep(i,1,n){
        if(deg[i]==1){
            q.push(i);
        }
    }
    while(SZ(q)>=2){
        int u=q.front();q.pop();
        int v=q.front();q.pop();
        ans[u]=v;
        ans[v]=u;
        for(auto &x:{u,v}){
            for(auto &y:e[x]){
                deg[y]--;
                if(deg[y]==1){
                    q.push(y);
                }
            }
        }
    }
    if(SZ(q)==1){
        int u=q.front();
        ans[u]=u;
    }
    rep(i,1,n){
        printf("%d ",ans[i]);
    }
    return 0;
}