題目

https://gmoj.net/senior/#main/show/6653

題目大意：

一棵有 n n n 個節點的以 1 1 1 為根的樹，令 p i p_i pi? 表示結點 i i i 的父親編號，那么它還滿足 p i < i p_i<i pi?<i ，把它每條邊的邊權以及除 1 1 1 以外每個點的 p i p_i pi? 取出，并且將它們 打亂順序 ，就能得到一個長度為 2 n ? 2 2n-2 2n?2 的序列 a a a ，

現在題目給出 n n n 和 a a a ，要求你輸出 n ? 1 n-1 n?1 個數，第 i i i 個數表示 n n n 到 1 1 1 之間有 i i i 條邊時， n n n 到 1 1 1 之間的最小邊權總和是多少，如果不存在滿足 n n n 到 1 1 1 之間有 i i i 條邊的樹，輸出 ? 1 -1 ?1 ，

滿足 1 ≤ n ≤ 1 0 5 , a i ∈ [ 1 , n ) ∪ Z 1\le n\le 10^5,a_i\in [1,n)\cup Z 1≤n≤105,ai?∈[1,n)∪Z ，

題解

部分分對正解啟發不大，就直接寫滿分做法了，

把 a a a 放進一個桶里，記這個桶為 B B B ，再用 S S S 表示它的前綴和，

考慮什么時候會無解（即不存在任意一棵操作后能變成 a a a 的樹），由于 p i < i p_i<i pi?<i ，即 [ 1 , i ] [1,i] [1,i] 中的每個數都會有一個在 [ 1 , i ) [1,i) [1,i) 中的父親，因此 S i ? 1 + 1 < i S_{i-1}+1<i Si?1?+1<i 時無解，

再考慮最短的 n → 1 n\to 1 n→1 的鏈會是怎么樣的呢？它的長度應該就是不得不選的數的數量，由于這時已經滿足 S i ? 1 ≥ i ? 1 S_{i-1}\ge i-1 Si?1?≥i?1 ，即 S i ≥ i S_i\ge i Si?≥i 若再有 S i ? 1 = i ? 1 S_{i-1}=i-1 Si?1?=i?1 ， i i i 就是必選的了，理由和上一條類似，由于只用關心這條鏈就好了，鏈上不可能有兩個點的父親一樣，因此每個數最多只選 1 1 1 次，至于為什么這些選擇的數一定可以構成一條鏈，這是因為選出了 p i p_i pi? 后，編號為 1 → n ? 1 1\to n-1 1→n?1 的點中哪些點會成為父親就已經知道了，共有 鏈的長度 -1 個點，把我們選出來的數放進這些位置就好了，剩下那個就是葉子，

求長度的話從大到小選擇沒有用過的數即可，

時間復雜度 O ( n ) O(n) O(n) ，

代碼

#include<cstdio>
using namespace std;
#define fo(i,l,r) for(i=l;i<=r;++i)
#define fd(i,r,l) for(i=r;i>=l;--i)
#define N 100005
long long ans[N];
int a[N],b[N],s[N];
bool fixed[N];
inline int mymin(int x,int y){return x<y?x:y;}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int i,j,l,r,t,x,n,m,len=0;
	scanf("%d",&n),m=2*n-2;
	fo(i,1,m) scanf("%d",&x),++a[x];
	fo(i,1,n-1) ans[i]=-1;
	fo(i,1,n-1) s[i]=s[i-1]+a[i];
	fo(i,1,n-1)
	{
		if(s[i-1]+1<i)
		{
			fo(j,1,n-1) printf("-1 ");
			return 0;
		}
		if(/*s[i]>=i&&*/s[i-1]<=i-1)
			fixed[i]=1,--a[i],++len;
	}
	j=len,ans[len]=0;
	fd(r,n-1,1)
	{
		t=mymin(a[r],j);
		a[r]-=t,j-=t,b[r]+=t,
		ans[len]+=r*t;
		if(!j) break;
	}
	fo(l,1,n-1) if((a[l]+b[l])&&!fixed[l])
	{
		fixed[l]=1;
		++len,ans[len]=ans[len-1],j=1;
		if(!a[l]) ans[len]-=l,++a[l],--b[l],++j;
		--a[l];
		while(r)
		{
			t=mymin(a[r],j);
			a[r]-=t,j-=t,b[r]+=t,
			ans[len]+=r*t;
			if(!j) break;
			--r;
		}
		if(len==n-1) break;
	}
	fo(i,1,n-2) printf("%lld ",ans[i]);
	printf("%lld\n",ans[n-1]);
	return 0;
}