OI - Acesrc and Travel (HDU)

开新坑啦! TAT
换根DP结合博弈论真的恶心……


Part1. 题面

> 传送门 HDU

有一棵 n 个点的无根树,每个点 u 有两个非负点权 $A_u,B_u$。

Alice 和 Bob 在这棵树上博弈,Alice 先手。第一次操作,先手在树上选任意一个点;然后接下来的操作,每次操作只能选取与上一次 选取的点相邻的、且没有被选过的点。一直选择直到没有可以选择的点为止。

每选择一个点 u(无论是 Alice 还是 Bob 选),Alice 的得分增加 $A_u$,Bob 的得分增加 $B_u$。

两人都希望“自己的得分减对手的得分”尽可能大。假设两人绝顶聪明(awa),输出最终 “Alice 的得分-Bob的得分”。

数据规模:$1\le n\le10^5$;$0\le A_u,B_u\le10^9$。


Part2. 解析

首先分析题目,因为除去第一次可以随意选择,其他操作都必须选择与上一次操作相邻的点,而且不能选择已经选过的点 —— 不难发现最后选出来的是树上的一条。新定义点 u 的点权为 $(A_u-B_u)$,显然 Alice 要让选出的链上的点权之和增大,Bob 要让它变小。

因为两人都绝顶聪明,那么其实 Alice 走了第一步,之后的所有最优方案都是唯一的。于是决定答案的 其实是第一次选择的点。

所以可以这样理解问题 —— 将第一个选择的点作为树的根节点,然后求出一条从根到叶子节点的链。从这一点可以考虑换根DP

在树上找链的换根 DP 有两个 dp 数组,f[u][..] 存储的是从 u 开始向子树连接链的答案信息,g[u][..] 存储的是从 u 往祖先跑(可能又折返往另一个子树)连成链的答案信息。两个合起来就能变成一条完整的链,这是这一类型的换根DP的常规套路。

注意到计算 f[u][..] 时,是从下往上递归计算,计算 g[u][..] 时,是从上往下计算

> Tip
举一个生动形象的栗子:
png1

很多这一类型的题会存储最大值和次大值,这道题也不例外。而且因为这是博弈论,Bob 要最小化链上点权和,而 Alice 要最大化它,所以这道题 f[u][..] 要维护 4 个值:

> Tab
v 是 u 的儿子节点

  1. f[u][0]:Bob 选 u,Alice 选择 u 的儿子 v,能够取得的最大值(不包含u本身的点权);
  2. f[u][1]:Bob 选 u,Alice 选择 v,能够取得的次大值(不包含u本身);
  3. f[u][2]:Alice 选 u,Bob 选择 v,能够取得的最小值(不包含u);
  4. f[u][3]:Alice 选 u,Bob 选择 v,能够取得的次小值(不包含u);

然后考虑 v 的 dp 值怎么更新 u 的 DP 值:

  1. 如果 Alice 选了 u,对应的 dp 数组为 f[u][2/3]
    那么 v 是由 Bob 选的,于是 Bob 会最小化 f[u][2/3]
    v 之后的一个节点是 Alice 选的,于是 Alice 会最大化从 v 开始的链,也就是取到最大值 f[v][0],再加上 v 的值 val[v]
    f[u][2/3] 分别保存了 f[v][0]+val[v] 的最小值和次小值。

  2. 如果 Bob 选了 u,对应的 dp 数组为 f[u][0/1]
    那么 v 是由 Alice 选的,于是 Alice 会最大化 f[u][0/1]
    v 之后的一个节点是 Bob 选的,于是 Bob 会最小化从 v 开始的链,则取到最小值 f[v][2],再加上 v 的值 val[v]
    f[u][0/1] 分别保存了 f[v][2]+val[v] 的最大值和次大值。

具体像下面这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(v==fa) continue;
DFSF(v,u);

//Bob choose u , Alice choose v
if(f[v][2]+val[v]>f[u][0])
f[u][1]=f[u][0],fp[u][1]=fp[u][0],
f[u][0]=f[v][2]+val[v],fp[u][0]=v;
else
if(f[v][2]+val[v]>f[u][1])
f[u][1]=f[v][2]+val[v],fp[u][1]=v;

//Alice choose u , Bob choose v
if(f[v][0]+val[v]<f[u][2])
f[u][3]=f[u][2],fp[u][3]=fp[u][2],
f[u][2]=f[v][0]+val[v],fp[u][2]=v;
else
if(f[v][0]+val[v]<f[u][3])
f[u][3]=f[v][0]+val[v],fp[u][3]=v;
}

要特殊处理叶子节点,把它的 f[u][0]f[u][2] 赋为 0。

然后就要计算 g[u][..] 了,这个就不需要最小和次小了,只计算:

  1. g[u][0] 表示 Alice 选点 u 时,Bob 选 u 的父亲,然后往上找链得到的最小值;
  2. g[u][1] 表示 Bob 选点 u 时,Alice 选 u 的父亲,往上找链得到的最大值;

然后考虑从 g[u][..] 怎么计算 g[v][..]

  1. 如果 Alice 选 v,那么 u 是 Bob 选的,u 之后的点是 Alice 选的:

    于是 Alice 会最大化 u 开始往上的链,要么是 g[u][1]+val[u],要么是 f[u][0/1]+val[u]

    比如这样(u 是 Bob 选的,绿色点是由 Alice 决定的):png2

  2. 反过来,如果 Bob 选 v,那么 u 是 Alice 选的,u 之后的点是 Bob 选:

    于是 Bob 会最小化从 u 开始往上的链,要么是 g[u][0]+val[u] 要么是 f[u][2/3]+val[u]

    同理嘛……

但是默认的根节点 1 比较特殊,因为它不存在向上的链,那么 g[1][..] 就没有定义,特别讨论一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//gA 表示 u 是 Alice 选的,即 g[u][0];gB 则是 g[u][1]
if(u==1){
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(deg[u]==1) DFSG(v,u,val[u],val[u]);
else{
ll gA_,gB_;
//根节点就不存在 g[1][..]
if(fp[u][0]!=v) gA_=f[u][0];
else gA_=f[u][1];
if(fp[u][2]!=v) gB_=f[u][2];
else gB_=f[u][3];
DFSG(v,u,gA_+val[u],gB_+val[u]);
}
}
return;
}
if(deg[u]==1) return; //deg[] 为度数,这里就是判断叶子节点
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(v==fa) continue;
ll gA_=gB,gB_=gA;
if(fp[u][0]!=v) gA_=max(gA_,f[u][0]);
else gA_=max(gA_,f[u][1]);
if(fp[u][2]!=v) gB_=min(gB_,f[u][2]);
else gB_=min(gB_,f[u][3]);
DFSG(v,u,gA_+val[u],gB_+val[u]);
}

最后就要统计答案了,可能有以下几种情况:

  1. 对于一般的节点,如果它是 Alice 开局选的节点,那么 Bob 会从可取的方案中,选取到 min(g[u][0],f[u][2])+val[u]

    png3

  2. 对于根节点,没有 g[u][0]

  3. 对于叶子节点,没有 f[u][2]

是不是很简单?(反正我觉得是真的绕,尤其是 max 和 min……)


Part3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=1e5;
const ll INF=(1ll<<60);

struct TNODE{
int to;TNODE *nxt;
TNODE(){}
TNODE(int _t,TNODE *_n):to(_t),nxt(_n){}
};
struct TREE{
TNODE pol[N*2+3],*head[N+3],*ncnt;
void Init(int n){
for(int i=1;i<=n;i++)
head[i]=NULL;
ncnt=pol;
}
void AddEdge(int u,int v){
TNODE *p=++ncnt,*q=++ncnt;
*p=TNODE(v,head[u]);head[u]=p;
*q=TNODE(u,head[v]);head[v]=q;
}
TNODE* operator [](int id){return head[id];}
}T_;

int cas,n;
ll ans;
int val[N+3],deg[N+3];
ll f[N+3][4];int fp[N+3][4];

int QRead(){
int resu=0;char ch=getchar();
while('0'>ch || ch>'9') ch=getchar();
while('0'<=ch && ch<='9') resu=(resu<<1)+(resu<<3)+ch-'0',ch=getchar();
return resu;
}
void DFSF(int u,int fa){
fp[u][0]=fp[u][1]=fp[u][2]=fp[u][3]=0;
f[u][0]=f[u][1]=-INF;f[u][2]=f[u][3]=INF;
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(v==fa) continue;
DFSF(v,u);
//f[u][0]>f[u][1] f[u][2]<f[u][3]

//Bob choose u , Alice choose v
if(f[v][2]+val[v]>f[u][0])
f[u][1]=f[u][0],fp[u][1]=fp[u][0],
f[u][0]=f[v][2]+val[v],fp[u][0]=v;
else
if(f[v][2]+val[v]>f[u][1])
f[u][1]=f[v][2]+val[v],fp[u][1]=v;

//Alice choose u , Bob choose v
if(f[v][0]+val[v]<f[u][2])
f[u][3]=f[u][2],fp[u][3]=fp[u][2],
f[u][2]=f[v][0]+val[v],fp[u][2]=v;
else
if(f[v][0]+val[v]<f[u][3])
f[u][3]=f[v][0]+val[v],fp[u][3]=v;
}
if(deg[u]==1 && u!=1)
f[u][0]=f[u][2]=0;
}
void DFSG(int u,int fa,ll gA,ll gB){
if(u==1){
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(deg[u]==1) DFSG(v,u,val[u],val[u]);
else{
ll gA_,gB_;
if(fp[u][0]!=v) gA_=f[u][0];
else gA_=f[u][1];
if(fp[u][2]!=v) gB_=f[u][2];
else gB_=f[u][3];
DFSG(v,u,gA_+val[u],gB_+val[u]);
}
}
ans=max(ans,f[u][2]+val[u]);
return;
}
if(deg[u]==1){
ans=max(ans,gA+val[u]);
return;
}
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(v==fa) continue;
ll gA_=gB,gB_=gA;
if(fp[u][0]!=v) gA_=max(gA_,f[u][0]);
else gA_=max(gA_,f[u][1]);
if(fp[u][2]!=v) gB_=min(gB_,f[u][2]);
else gB_=min(gB_,f[u][3]);
DFSG(v,u,gA_+val[u],gB_+val[u]);
}
ans=max(ans,val[u]+min(gA,f[u][2]));
}
int main(){
cas=QRead();
while(cas--){
n=QRead();
T_.Init(n);
for(int i=1;i<=n;i++) val[i]=QRead(),deg[i]=0;
for(int i=1;i<=n;i++) val[i]-=QRead();
for(int i=1;i<n;i++){
int u,v;
T_.AddEdge(u=QRead(),v=QRead());
deg[u]++,deg[v]++;
}
if(n==1){
printf("%d\n",val[1]);
continue;
}
DFSF(1,0);
ans=-INF;
DFSG(1,0,0,0);
printf("%lld\n",ans);
}
return 0;
}

The End

Thanks for reading!

写了恶心题没有心情写题了……写篇博客调整心态 :)

0%