BUPT2017 wintertraining(15) #7FMinimax Tree
题意
给你一棵多叉树，非叶子节点中分配k个为子节点的min函数，剩下的是max函数。
现在求根节点（1）的最大值和最小值。
题解
因为最大值和最小值求法对称，以求最小值为例。
要让尽量小的上来，可以贪心选择一条路前面都是min不够了后面就用max。
因为如果min上面有max，max换到下面不会更差。
但是这条前面都是min的路选哪一条呢？显然是最后一个min节点的子节点里max取最小的。
共k个min，所以取第k+1层所有节点的max函数的最小值。
但是，如果有的叶子深度小于k，是可以直接达到的，所以要取这些叶子的最小值更新答案。
但是，如果一个节点只有一个子节点，原来认为一条路前面都选min的贪心就不成立了，如
得到5 得到2 min min
+ +
| |
+----+----+ +----+----+
| | | |
v v min v v max
5 | 5 |
v max v max
| |
v max v max
| |
v max v min
| |
+--+---+ +--+---+
v v v v
2 7 2 7
把每个单子节点深度设为父节点的深度，这样就可以计算出正确答案。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
const int inf = 1e9+1;
struct edge{
int to,next;
}e[N<<1];
int cnt,head[N];
void add(int fa,int son){
e[++cnt]=(edge){son, head[fa]};
head[fa]=cnt;
}
int ma[N], mi[N], dma[N], dmi[N];
int n,k;
int dep[N];
int son[N];
void dfs(int x, int fa){
dep[x]=dep[fa]+(son[fa]!=1);
for(int i=head[x]; i; i=e[i].next){
dfs(e[i].to, x);
mi[x]=min(mi[x], mi[e[i].to]);
ma[x]=max(ma[x], ma[e[i].to]);
}
dmi[dep[x]]=min(dmi[dep[x]],ma[x]);
dma[dep[x]]=max(dma[dep[x]],mi[x]);
}
bool noleaf[N];
int main(){
scanf("%d%d",&n,&k);
for(int i=2;i<=n;++i){
int p;
scanf("%d",&p);
noleaf[p]=true;
++son[p];
add(p,i);
}
for(int i=1;i<=n;++i)dmi[i]=inf;
int leaf=0;
for(int i=1;i<=n;++i){
int a;
scanf("%d",&a);
if(!noleaf[i]){
mi[i]=ma[i]=a;
++leaf;
}else{
mi[i]=inf;
}
}
dfs(1,0);
intans1=dmi[k+1], ans2=dma[n-leaf-k+1];
for(int i=1;i<=n;++i)if(!noleaf[i]){
if(dep[i]<k+1)ans1=min(ans1, mi[i]);
if(dep[i]<n-leaf-k+1)ans2=max(ans2, mi[i]);
}
printf("%d %d", ans1, ans2);
return 0;
}
