覺的不寫博客不行了，要不然以后都忘了= =

大體題意:

給你一個完全二叉樹，標號為層次標號1~n，定義一個a(0<= a < k) ，要求選出一個子樹來（結點為V1,V2,V3,,VK）值為V(k-a+1)/2的權重。

求每個a的最大值。

思路：

題意很繞，比賽沒做出來。

觀察a的值，(k-a+1)/2 這是1~ (k-a)的中位數。

觀察圖發現：

我們可以把中位數x左邊的標成-1，右邊的都標成+1

那么這個子樹的權值之和就是a 。

可能大家覺得不好處理，應該是權值之和-1或者-2

但是換個角度考慮：

假設權值之和為W，那么我們就可以按照這個圖的形式 進行重分配：

根據a和k的范圍，k-a 至少為1，a至少為0

那么a的值就是0~ W-1

這樣我們把0~W-1  a的值全都變成X即可。

這樣我們只需要 倒著枚舉X，每次更新X所在的祖先鏈的dp值（dp記錄的是子樹最大權值之和），因為是一個完全二叉樹， logn 即可達到根。然后在更新一下a數組。

復雜度大約nlogn  更新a數組要優化，一旦發現有一個賦值過了，就不用在循環了。

反正大于nlogn   加上那個優化 就不會超時了。

詳細見代碼：

#include <cstdio>#include <cstring>#include <algorithm>#define Max(a,b) ((a)>(b)?(a):(b))using namespace std;const int maxn = 2e5+7;int n;int a[maxn], ans[maxn], dp[maxn][2], w[maxn];void DP(int v,int u){    w[v] = 1;    for (int o = v; o; o >>= 1){        int ls = o << 1, rs = o << 1 | 1;        dp[o][1] = w[o];        dp[o][0] = 0;        if (ls <= n){            dp[o][1] += Max(0, dp[ls][1]);            dp[o][0] = Max(dp[o][0], Max(dp[ls][1],dp[ls][0]));        }        if (rs <= n){            dp[o][1] += Max(0, dp[rs][1]);            dp[o][0] = Max(dp[o][0], Max(dp[rs][1],dp[rs][0]));        }    }    int x = Max(dp[1][0] , dp[1][1]);    for (int i = x-1; i >= 0; --i){        if (ans[i])return; /// 不要重復賦值，雖然感覺優化不好，但是快了好多好多好多= =。        ans[i] = u;    }}int main(){    while(~scanf("%d",&n)){        for (int i = 1; i <= n; ++i) {            int x;            scanf("%d",&x);            a[x] = i;            w[i] = -1;            dp[i][0] = dp[i][1] = 0;            ans[i-1] = 0;        }        for (int i = n; i >= 1; --i){            DP(a[i],i);        }        for (int i = 0; i < n; ++i){            if (i) PRintf(" ");            printf("%d",ans[i]);        }        puts("");    }    return 0;}/**51 2 3 4 5109 10 4 2 3 5 7 1 8 6**/