题目描述
传送门
题目大意：给出一个有根树，A，B两个人轮流操作。 给每个叶子节点分配权值[1..叶子节点数]的一个排列。每次每个人可以选择任意一条边走，A希望最后取得的叶子节点的权值尽可能大，B希望最后取得的叶子节点的权值尽可能的小，两个人都绝对聪明，问如果让A分配权值最后能得到的最大权值是多少，如果让B分配权值最后能得到的最小权值是多少。
题解
已A的操作为例。 f[i]表示到达节点i能获得其子树中第几大的权值。显然A可以控制奇数层的节点，B可以控制偶数层的节点。 轮到A操作的时候，他一定会选择
min(f[son])
，安排权值的时候把所有最大的都放置到一棵子树上。 轮到B操作的时候，他会尽可能选择小的，所以A的目标就是使最小值最大，那么最好的方式就是平均分配。 最后B只能得到
∑f[son]
B的操作也是一样的，不过用f[i]表示第几小即可。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 400003
using namespace std;
int n,tot,nxt[N],v[N],point[N],f[N],deep[N],leaf;
void add(
int x,
int y)
{
tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
void dfs_A(
int x,
int fa)
{
deep[x]=deep[fa]+
1;
bool pd=
false;
if (deep[x]&
1) {
f[x]=n;
for (
int i=point[x];i;i=nxt[i]) {
if (v[i]==fa)
continue;
dfs_A(v[i],x);
f[x]=min(f[x],f[v[i]]);
pd=
true;
}
}
else {
for (
int i=point[x];i;i=nxt[i]){
if (v[i]==fa)
continue;
dfs_A(v[i],x);
f[x]=f[x]+f[v[i]];
pd=
true;
}
}
if (!pd) f[x]=
1,leaf++;
}
void dfs_B(
int x,
int fa)
{
bool pd=
false;
if (!(deep[x]&
1)){
f[x]=n;
for (
int i=point[x];i;i=nxt[i]) {
if (v[i]==fa)
continue;
dfs_B(v[i],x);
f[x]=min(f[x],f[v[i]]);
pd=
true;
}
}
else {
f[x]=
0;
for (
int i=point[x];i;i=nxt[i]){
if (v[i]==fa)
continue;
dfs_B(v[i],x);
f[x]=f[x]+f[v[i]];
pd=
true;
}
}
if (!pd) f[x]=
1;
}
int main()
{
freopen(
"a.in",
"r",stdin);
scanf(
"%d",&n);
for (
int i=
1;i<n;i++) {
int x,y;
scanf(
"%d%d",&x,&y);
add(x,y);
}
dfs_A(
1,
0);
printf(
"%d ",leaf-f[
1]+
1);
dfs_B(
1,
0);
printf(
"%d\n",f[
1]);
}
