[POI 19 Stage 3] Salaries

作法：

顯然這些值會構成一個 heap 。首先觀察到一件重要的事實：如果一個節點 u 的值確定了，但他的子節點個數 > 1，那麼 u 的所有子孫一定都是不確定的。因為對於 u 的任意一個子孫 v，我們一定可以把他和 u 的另一個子樹裡的點的值交換( 滿足交換的兩個節點的 LCA 是 u  )，並且用維護 heap 的方法把該往上浮的往上浮，該往下沉的往下沉，就可以讓 v 上的值換成另一個值了。而這個交換的動作不會出問題是因為交換的兩個數都 < u ，所以可以保證交換之後往上浮的數不會把 u 給取代掉。

以下稱原本就已經確定值的點為黑點。再來會發現，我們可以把所有連接兩個黑點的邊全部都拔掉，把一顆樹拔成森林，因為對於拔完之後的每個子樹來說，他原本是落在拔邊之前的樹的哪裡並不重要，因為黑點們已經好好的滿足 heap 的性質了，重要的只剩下這棵子樹的形狀，和根上標的值了( 根是黑點 )。這邊我們會需要保證拔完之後的每個子樹的根都是黑的(並且他的子孫都不是黑的)，而不滿足這個條件的情況只有整棵樹都不是黑的，那麼對這個情況特別處理即可。

所以現在我們獲得了好幾個只有根為黑色的子樹，把他們按照根的值從小到大排序，記排完序後的子樹們分別是 T_1 , T_2 , ... , T_m ，並且 T_i 的根的值是 v_i ，還有所有還沒使用過的數的集合為 S ( 就是 1~n 扣掉黑點上已經標好的數們 )。先看 T_1 ，如果在 S 中小於 v_1 的數的個數和 T_1 中未確認的數的個數一樣多的話，那麼就可以確定 T_1 中未確認的數就是所有小於 v_1 的 S 裡的數。而對於每一個數我們可以先預處理出「小於他的在 S 裡的數有幾個」，並且對於每個子樹預處理出他的 size ，這樣「這個子樹中還沒確定的數的個數」就是 size -1 個，所以可以快速的判斷 T_1 是否滿足上述條件。所以當我們知道 T_1 中只有哪些數的時候，如果 T_1 的根有 > 1 個孩子，那麼這整棵樹的值的位置都是不確定的( 原因在一開始就有提到 )，而如果只有 1 個孩子的話，那麼根的孩子這個位置的數就確定了，他一定會是小於 v_1 的最大的還沒被用過的數。所以我們可以一路從 T_1 的根往下走，如果只有一個孩子就繼續走，沿路上遇到的都是值確定的節點，把他們的答案標記好即可。

如果小於 v_1 的 S 裡的數的個數不等於 T_1 中未確認的數的個數，那麼因為題目保證必定存在一種填法使得原本的樹形成一個 heap ，可以知道這時候必定有「小於 v_1 的 S 裡的數的個數」 > 「 T_1 中未確認的數的個數」，否則用那些數字就會沒辦法填完 T_1 底下的空格，產生矛盾。這時候T_1 裡的數一定全部都是位置不確定的，因為這時候必定有一個 < v_1 的數被放到其他子樹去了，那麼對於任意一個目前放在 T_1 裡的數，我們可以把他和放在別的子樹裡的某個 < v_1 的數交換，並浮沉維護好堆性質，並且一樣是因為交換過來的數 < v_1 ，所以可以保證他不會取代掉根。

於是由以上的結論就得到了這樣的算法：如果 k 是最小的數，滿足 T_1 , T_2 , ... , T_k 中，未確認的數的個數總和和小於 v_k 的 S 裡的數的個數相等 ( 注意到這樣的 k 必定存在，因為當 k = m ( 子數總個數 ) 的時候這件事顯然是對的 )，那麼 T_1 ~ T_(k-1) 中的所有數都是不確定的，而從 T_k 的根開始一路往下走，並且保持路上經過的節點都只有一個子節點，那麼路上的所有數都會是確定的。並且從 v_k 開始往下找哪個數還沒用過，依次填入 T_k 中。作完之後就會剩下 T_(k+1) ~ T_m ，而這時的情況和原本有 T_1 ~ T_m 的情況無異，所以可以套用一樣的算法，直到處理完所有的子樹為止。

但這樣做還有一個小問題，就是如果我們在把一個數 x 填入 T_k 時，發現 x < v_( k-1 ) ，那麼 x 就會變成不確定的了，因為這時 x 也可以被丟到 T_(k-1) 去，所以只要在出現這種情況的時候趕快 break 掉即可。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
struct P
{
    int id,val ;
    bool operator < (const P &rhs) const
    {
        return val<rhs.val ;
    }
};
 
int val[maxn],fa[maxn],sz[maxn] ;
vector<int> v[maxn] ;
 
void dfs(int x)
{
    sz[x]=1 ;
    for(int i=0;i<v[x].size();i++)
        dfs(v[x][i]) , sz[x]+=sz[v[x][i]] ;
}
 
P p[maxn] ;
int num[maxn] ;
 
main()
{
    int n,root ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) num[i]=1 ;
    bool none=0 ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&fa[i],&val[i]) ;
        if(val[i]) num[val[i]]=0 ;
        if(fa[i]==i && !val[i]) none=1 , root=i ;
        if(fa[i]!=i && !val[i]) v[fa[i]].push_back(i) ;
        else fa[i]=i ;
    }
    for(int i=1;i<=n;i++) num[i]+=num[i-1] ;
 
    if(none)
    {
        for(int i=root,j=n;;j--)
        {
            val[i]=j ;
            if(v[i].size()!=1) break ;
            i=v[i][0] ;
        }
        for(int i=1;i<=n;i++) printf("%d\n",val[i]) ;
        return 0 ;
    }
 
    for(int i=1;i<=n;i++) if(fa[i]==i)
        dfs(i) ;
 
    int cnt=0 ;
    for(int i=1;i<=n;i++) if(fa[i]==i && !v[i].empty())
        p[cnt++]=(P){i,val[i]} ;
    sort(p,p+cnt) ;
 
    for(int i=0,sum=0;i<cnt;i++)
    {
        sum+=sz[p[i].id]-1 ;
        int mi=-1 ;
        while(sum<num[p[i].val]) mi=p[i].val , i++ , sum+=sz[p[i].id]-1 ;
        for(int j=p[i].id,now=p[i].val;;now--)
        {
            if(v[j].size()!=1) break ;
            while(num[now]==num[now-1]) now-- ;
            j=v[j][0] ;
            if(now<mi) break ;
            else val[j]=now ;
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",val[i]) ;
}