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;
}