正題

題目鏈接:https://www.luogu.com.cn/problem/P7920

---

題目大意

一個排列$p$生成的森林的形式如下，對于每個$i$找到最大的$j\in [1,i)$滿足 $p_i>p_j$，然后連一條$i,j$之間的邊。
給出一張樹$G$，求一個字典序最大的排列$p$使得生成的樹與$G$同構(gòu)。

$1\le n\le 5000$

---

解題思路

先考慮暴力的方法，我們可以枚舉一個根，然后開始肯定根是$1$，然后子節(jié)點中假設(shè)大小都不相同我們肯定是從小到大放，因為假設(shè)現(xiàn)在放到$k$，那么每棵子樹的根放的肯定是$k?siz+1$（因為一個根要是子樹中最小的）。如果有大小相同的我們可以比較每棵內(nèi)部放好時的字典序然后從大到小放。

顯然這樣是三方的，我們需要優(yōu)化?？紤]到我們每次需要比較子樹的字典序大小，而對于所有根來說整棵就只有$2n?2$棵子樹（每條邊的正反方向的子樹），我們可以把這些子樹都拿出來比較。

先按照子樹大小排序，然后我們按照子樹大小從小到大排同大小子樹的順序，因為排大的子樹時需要用到小子樹的順序關(guān)系。

而且不難觀察到最優(yōu)的根一定是與某個葉子連接的點，同樣的這個葉子它的另一邊是一個大小為$n?1$的子樹，所以我們拿順序最小的大小為$n?1$的子樹出來輸出即可。

時間復(fù)雜度：$O(n^2\log n)$，但是由于子樹的字典序排序只會出現(xiàn)在同大小之間，所以常數(shù)很小，可以通過本題。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cctype> using namespace std; const int N=1e4+10; struct node{int id,siz;vector<int> v; }p[N]; struct edge{int to,next,from; }a[N]; int n,tot,ls[N],g[N],f[N],siz[N]; int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } bool cmp(int x,int y) {return f[x]<f[y];} bool cMp(node x,node y) {return x.siz<y.siz;} bool CmP(node x,node y){int l=min(x.v.size(),y.v.size());for(int i=0;i<l;i++)if(f[x.v[i]]!=f[y.v[i]])return f[x.v[i]]<f[y.v[i]];return 0; } void addl(int x,int y){a[++tot].to=y;a[tot].from=x;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa){siz[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);siz[x]+=siz[y];}return;} void print(int x,int k){for(int i=0;i<p[x].v.size();i++){printf("%d ",k-p[g[p[x].v[i]]].siz+1);print(g[p[x].v[i]],k);k-=p[g[p[x].v[i]]].siz;}return; } int main() {n=read();if(n==1)return puts("1")&0;for(int i=1;i<n;i++){int x=read(),y=read();addl(x,y);addl(y,x);}dfs(1,0);for(int z=1;z<=tot;z++){int x=a[z].from,y=a[z].to;p[z].siz=(siz[y]>siz[x])?(n-siz[x]):siz[y];for(int i=ls[y];i;i=a[i].next){int w=a[i].to;if(w==x)continue;p[z].v.push_back(i); }p[z].id=z;}sort(p+1,p+1+tot,cMp);int l=1,r=0,cnt=0;for(int S=2;S<n;S++){while(l<=tot&&p[l].siz<S)l++;while(r<tot&&p[r+1].siz<=S)r++;for(int x=l;x<=r;x++)sort(p[x].v.begin(),p[x].v.end(),cmp);sort(p+l,p+r+1,CmP);f[p[l].id]=++cnt;if(S==n-1)break;for(int x=l+1;x<=r;x++){cnt+=CmP(p[x-1],p[x]);f[p[x].id]=cnt;}}for(int i=1;i<=tot;i++)g[p[i].id]=i;printf("1 %d ",n);print(l,n-1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P7920-[Kubic]Permutation的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。