ICPCCamp2017 Day 3 F Median on Binary Tree（树dp）

觉的不写博客不行了，要不然以后都忘了= =

大体题意:

给你一个完全二叉树，标号为层次标号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**/