OI题解 - NOIP2018 保卫王国

按某一个炒鸡dalao名曰 taotao 的话说:

顺便提一下他的〔题解〕(因为按照这个思路写的,所以代码看起来也差不多)
因为比较复(胡)杂(炸),可能需要理解久一点


『题目』

参见 〔洛谷 P5024〕


『解析』

一、初步思考

如果不考虑多次询问的话,显然可以进行一次简单的树形DP,特殊判断一下当前的点(也就是城市)能不能选(放军队)就行了~ 但是显然会$TLE$。
由于$m$也就是询问次数非常大,而dp状态非常之多,不可能 $O(1)$ 的时间处理每次询问。那么剩下两种时间复杂度的可能性要么是 $O(log_2n)$ 要么是 $O(\sqrt{n})$。根据我浅薄的对算法的理解……好像没有什么用来优化dp的有关树的算法是 $O(\sqrt n)$ 的,倒是有一个树上倍增($LCA$)是 $O(log_2n)$ 的。

(至于一般的树形dp相信大家都会)

对这道题本身进行分析——假设现在被限制的点是 $u$,$v$ ,根节点是 $1$,那么:
① $lca$ 到 点$1$ 的路径上的 $dp$ 值被 $u$,$v$ 共同影响;
② $u$ 到 $lca$ 的路径上的 $dp$ 值被 $u$ 影响;
③ $v$ 到 $lca$ 的路径上的 $dp$ 值被 $v$ 影响;

恰好我们知道有一种倍增优化dp的算法,所以正解顺理成章就是树上倍增优化树形dp~(出题人的思维还是非常厉害的)

对于倍增求lca的运用不止可以求出lca,还经常用来统计两点经过lca的简单路径上的一些特殊值,其转移方法大多数是:

如果要求 u 到 u的第$2^i$个祖先 的路径上的值,就综合 u 到 u的第$2^{i-1}$个祖先 的路径上的值,和 u的第$2^{i-1}$个祖先 到 u的第$2^i$个祖先 的路径上的值;

二、倍增推导dp数组

那么对树形dp的优化也是这样的~因为一般的dp状态定义是 “dp[u][0/1] 表示u选/不选时以u为根的子树的最小花费”,那么我们定义 $fdp[u][k][0/1][0/1]$ 表示 “u选/不选(第三维)”并且 u的第$2^i$个祖先 选/不选(第四维)时,以 u的第$2^i$个祖先 为根的子树的最小花费。另外几个定义如下:

  • $fa[u][i]$ 表示“点u的第$2^i$个祖先”,如果没有则值为0;
  • $dep[u]$ 表示“点u的深度”;

一次DFS就可以求出 dp,dep 的值(DFS1)。

因为我们考虑了2个点的取舍,必然就会有一些之前的(没有任何限制时的最优值)是不合法的,所以我们需要对 fdp 进行一些修改。这就进入了第2次DFS:

根据 taotao 的说法,大概就是“合法的值=可能不合法的值-原有贡献+合法的贡献”

倍增求lca的基本操作——先把 u 到 u的父亲 的值处理出来,然后依次处理出 fa和fdp 。也就是说我们先要处理 $fdp[u][0][0/1][0/1]$ ,以下简称pre为u的父亲:

  • fdp[u][0][0/1][0/1]=INF :因为 u 和 pre 至少有一个要选;
  • fdp[u][0][1][0]=dp[pre][0] :因为如果pre不选那么u一定选
  • fdp[u][0][0][1]=dp[pre][1]-min(dp[u][0],dp[u][1])+dp[u][0]:因为选pre时,u的贡献为min(dp[u][0],dp[u][1]),但是我们必须限制u不选,所以减去它原有贡献再加上dp[u][0]也就是合法贡献;
  • fdp[u][0][1][1]=dp[pre][1]-min(dp[u][0],dp[u][1])+dp[u][1]:其他的都和上面的那种情况是相同的,只不过这是限制了u必须选也就是必须产生dp[u][1]的贡献。

重要的不是递推式,是思路“合法的值=可能不合法的值-原有贡献+合法的贡献”——
假设我们现在要推导从u到u的第2^k个祖先的状态,也就是fdp[u][k][a][b](a决定u选/不选,b决定u的第2^k个祖先选/不选)
那么,我们可以根据已经得到的
①u到u的第2^{k-1}个祖先(定义为anc)的状态也就是fdp[u][k-1][a][0/1]
②anc到anc的第2^{k-1}个祖先的状态也就是fdp[anc][k-1][0/1][b]
可见anc有两种状态——选/不选,那么我们定义这个状态为c
① 那么上面说的“可能不合法的值”是指fdp[anc][k-1][c][b],因为我们并不知道这个值所代表的状态是否满足u的状态;
② “原有贡献”也就是dp[anc][c],在这种状态下,u的状态是不受限制的;
③ “合法的贡献”说的是fdp[u][k-1][a][c],这样的话也就限制了u的状态

综上所述,我们可以得到转移式:

(感觉开始difficult了)
这样的话我们就可以转移了~这就是第二次DFS(DFS2)。

三、lca求解答案

接下来就是求LCA,顺便求解答案的过程——类比之前的转移,这里的转移要点也是“合法的值=可能不合法的值-原有贡献+合法的贡献”;只是说这里的转移可以大致分为3步(下面都假设u的深度大于v):

  1. 将u移动到与v深度相同的位置,移动的路径就是u的状态会影响的路径;
  2. 将u,v同时移动到它们的lca,u,v各自移动的路径分别受u,v的状态的影响;
  3. 将lca移动到根节点,lca移动的路径由u,v的状态共同影响;

那么我们设在限制下,当前的以u(这里强调“当前”是因为u在不断移动)为根的子树的最小花费为 val[1](选择u) 和 val[2](不选择u);以及当前的以v为根的子树的 val[3] 和 val[4]。然后在定义一个fval[1~4]分别对应val[1~4],方便转移~

(1)将u移动到与v同层

这里涉及到的变量有 u 对应的状态 val[1],val[2],以及 u 将要移动到的位置对应的状态 fval[1],fval[2]。
假设现在要将u移动到u的第$2^i$个祖先,显然u的状态可以选也可以不选,那么定义a为u的状态:

对于fval[1],这里的“可能不合法的值”是fdp[u][i][a][1](因为不知道是否满足限制),“原有贡献”为dp[u][a],“合法贡献”为val[a](u的状态对应的val值);当然fval[2]也可以类比上面的方法。

(2)将u,v同时移动到lca

和(1)相同,只是多了v也要同时转移~(也就是说还涉及到val[3],val[4])
但是有一种特殊情况——v是u的祖先,这样的话根据v的限制,我们就需要舍去一个val值:
现在的val[1],val[2]也就是lca选/不选所对应的值,但是如果v就是lca,v就会对val产生限制,也就是说当v不能选时,表示选的val[1]就要被舍去,而当v必须选时,表示不选的val[2]就要被舍去。

(3)将lca移动到根节点

完全一样了,这里的lca就代替了u,val[1],val[2]分别指lca选/不选时以lca为根的子树的花费。
最后得到答案就是min(val[1],val[2])

(感觉好难讲懂啊 $QwQ$,不如先看一看代码?)


『源代码』

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
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000;
const ll INF=(1ll<<60);
struct GRAPH{
struct NODE{
int to,nxt;
NODE(){}
NODE(int _to,int _nxt):to(_to),nxt(_nxt){}
}edg[N*2+5];
int edgtot,adj[N+5];
void Init(){
edgtot=0;
memset(adj,-1,sizeof adj);
}
void AddEdge(int u,int v){
edg[++edgtot]=NODE(v,adj[u]);
adj[u]=edgtot;
}
}grp;
int n,m;
int cst[N+5],dep[N+5],fa[N+5][23];
ll dp[N+5][2],fdp[N+5][23][2][2];
void DFS1(int u,int pre){
dep[u]=dep[pre]+1;
dp[u][0]=0;dp[u][1]=cst[u];
for(int it=grp.adj[u];it!=-1;it=grp.edg[it].nxt){
int v=grp.edg[it].to;
if(v==pre) continue;
DFS1(v,u);
dp[u][0]+=dp[v][1];
dp[u][1]+=min(dp[v][0],dp[v][1]);
}
}
void DFS2(int u,int pre){
fa[u][0]=pre;
fdp[u][0][0][0]=INF;
fdp[u][0][1][0]=dp[pre][0];
fdp[u][0][0][1]=dp[pre][1]-min(dp[u][0],dp[u][1])+dp[u][0];
fdp[u][0][1][1]=dp[pre][1]-min(dp[u][0],dp[u][1])+dp[u][1];
for(int i=1;i<20;i++){
int anc=fa[u][i-1];
fa[u][i]=fa[anc][i-1];
fdp[u][i][0][0]=min(fdp[anc][i-1][0][0]-dp[anc][0]+fdp[u][i-1][0][0],fdp[anc][i-1][1][0]-dp[anc][1]+fdp[u][i-1][0][1]); //u -> anc -> fa[anc][i-1]
fdp[u][i][1][0]=min(fdp[anc][i-1][0][0]-dp[anc][0]+fdp[u][i-1][1][0],fdp[anc][i-1][1][0]-dp[anc][1]+fdp[u][i-1][1][1]);
fdp[u][i][0][1]=min(fdp[anc][i-1][0][1]-dp[anc][0]+fdp[u][i-1][0][0],fdp[anc][i-1][1][1]-dp[anc][1]+fdp[u][i-1][0][1]);
fdp[u][i][1][1]=min(fdp[anc][i-1][0][1]-dp[anc][0]+fdp[u][i-1][1][0],fdp[anc][i-1][1][1]-dp[anc][1]+fdp[u][i-1][1][1]);
}
for(int it=grp.adj[u];it!=-1;it=grp.edg[it].nxt){
int v=grp.edg[it].to;
if(v==pre) continue;
DFS2(v,u);
}
}
ll LCA(int u,int v,int U,int V){
if(dep[u]<dep[v]) swap(u,v),swap(U,V);
ll val[5]={0,(U? dp[u][1]:INF),(U? INF:dp[u][0]),(V? dp[v][1]:INF),(V? INF:dp[v][0])};
ll fval[5];
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v]){
fval[1]=min(fdp[u][i][0][1]-dp[u][0]+val[2],fdp[u][i][1][1]-dp[u][1]+val[1]);
fval[2]=min(fdp[u][i][0][0]-dp[u][0]+val[2],fdp[u][i][1][0]-dp[u][1]+val[1]);
val[1]=fval[1];val[2]=fval[2];
u=fa[u][i];
}
int lca;
if(u==v){
if(V) val[2]=INF;
else val[1]=INF;
lca=v;
}
else{
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i]){
fval[1]=min(fdp[u][i][0][1]-dp[u][0]+val[2],fdp[u][i][1][1]-dp[u][1]+val[1]);
fval[2]=min(fdp[u][i][0][0]-dp[u][0]+val[2],fdp[u][i][1][0]-dp[u][1]+val[1]);
fval[3]=min(fdp[v][i][0][1]-dp[v][0]+val[4],fdp[v][i][1][1]-dp[v][1]+val[3]);
fval[4]=min(fdp[v][i][0][0]-dp[v][0]+val[4],fdp[v][i][1][0]-dp[v][1]+val[3]);
val[1]=fval[1];val[2]=fval[2];val[3]=fval[3];val[4]=fval[4];
u=fa[u][i];v=fa[v][i];
}
lca=fa[u][0];
fval[1]=dp[lca][1]-min(dp[u][1],dp[u][0])-min(dp[v][1],dp[v][0])+min(val[1],val[2])+min(val[3],val[4]);
fval[2]=dp[lca][0]-dp[u][1]-dp[v][1]+val[1]+val[3];
val[1]=fval[1];val[2]=fval[2];
}
for(int i=19;i>=0;i--)
if(dep[fa[lca][i]]>=dep[1]){
fval[1]=min(fdp[lca][i][0][1]-dp[lca][0]+val[2],fdp[lca][i][1][1]-dp[lca][1]+val[1]);
fval[2]=min(fdp[lca][i][0][0]-dp[lca][0]+val[2],fdp[lca][i][1][0]-dp[lca][1]+val[1]);
val[1]=fval[1];val[2]=fval[2];
lca=fa[lca][i];
}
return min(val[1],val[2]);
}
int main(){
grp.Init();
scanf("%d%d%*s",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&cst[i]);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
grp.AddEdge(u,v);grp.AddEdge(v,u);
}
DFS1(1,0);
DFS2(1,0);
while(m--){
int u,v,U,V;scanf("%d%d%d%d",&u,&U,&v,&V);
if((fa[u][0]==v || fa[v][0]==u) && (!U && !V)){
printf("-1\n");
continue;
}
printf("%lld\n",LCA(u,v,U,V));
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%