OI - Boboniu and Jianghu(Codeforces) | Lucky_Glass's Blog
0%

OI - Boboniu and Jianghu(Codeforces)

树锯结构~


# 题面

点击展开/折叠 题面

有一棵 $n$ 个点的树($1\le n\le 2\times10^5$),第 $i$ 个点有参数 $a_i,b_i$。($1\le a_i,b_i\le10^6$)

现在要求把这棵树剖分成若干条链(链包括端点),使每条边恰好出现在一条链中,且要求链上的点的 $b_i$ 单调不降或单调不增。一条链的权值定义为链上所有点的 $a_i$ 之和。

求在所有剖分方案中,链的总权值最小为多少。


# 解析

所谓单调递增或单调递减,其实只用看成一条有向的链,$a_i$ 大的点指向 $a_i$ 小的点即可。

若 $a_u\neq a_v$ ,则边 $(u,v)$ 的方向是固定的。不妨假设所有边的方向都固定了,设点 $u$ 的入度为 $p_u$、出度为 $q_u$,则在最优的情况下 $u$ 会在 $\max\{p_u,q_u\}$ 条有向链中产生一次贡献(即尽可能将入边与出边匹配)。

但是如果 $a_u=a_v$,则需要确定 $(u,v)$ 的方向。注意到对于一个点,重要的只有其入度和出度,因此考虑树形DP。

$f_{u,0}$ 表示 $u$ 到其父节点的边是从 $u$ 连“出”,$f_{u,1}$ 表示连“入”到 $u$。

接下来就是比较套路的DP方法。在 $u$ 点转移时,设其子节点 $v_1,v_2,\dots,v_k$ 的边需要定向,则先全部定向为从 $u$ 指向 $v_i$;再考虑改变一条边的方向,使得DP值的变化最小,即取 $f_{v,0}-f_{v,1}$ 最小的 $v$ 改变方向,计算答案。

对 $v_1,v_2,\dots,v_k$ 按 $f_{v,0}-f_{v,1}$ 从小到大排序,依次改变边的方向,维护此时的 $p_u,q_u$,从而求出 $u$ 的DP值。

总复杂度 $O(n\log n)$,即每个点排序的复杂度。


# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=2e5+10;
const ll INF=(1ll<<60);
#define ci const int &

int n;
int hgt[N],val[N];
ll f[N][2],tmp[N],ans;

struct GRAPH{
int head[N],to[N<<1],nxt[N<<1],ncnt;
void AddEdge(ci u,ci v){
int p=++ncnt,q=++ncnt;
to[p]=v,nxt[p]=head[u],head[u]=p;
to[q]=u,nxt[q]=head[v],head[v]=q;
}
inline int operator [](ci u){return head[u];}
}Gr;

inline int Read(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r;
}
//0:up ; 1:down
void DP(ci u,ci fa){
ll sum=0;
f[u][0]=f[u][1]=INF;
int in=0,out=0;
for(int it=Gr[u];it;it=Gr.nxt[it]){
int v=Gr.to[it];
if(v==fa) continue;
DP(v,u);
if(hgt[v]<hgt[u]) sum+=f[v][0],in++;
if(hgt[v]>hgt[u]) sum+=f[v][1],out++;
}
int ntmp=0;
for(int it=Gr[u];it;it=Gr.nxt[it]){
int v=Gr.to[it];
if(v==fa || hgt[v]!=hgt[u]) continue;
sum+=f[v][1];
tmp[++ntmp]=f[v][0]-f[v][1];
out++;
}
sort(tmp+1,tmp+1+ntmp);
for(int i=0;i<=ntmp;i++,in++,out--,sum+=tmp[i]){
if(u==1)
ans=min(ans,sum+1ll*max(in,out)*val[u]);
else{
f[u][0]=min(f[u][0],sum+1ll*max(in,out+1)*val[u]);
f[u][1]=min(f[u][1],sum+1ll*max(in+1,out)*val[u]);
}
}
}
int main(){
n=Read();
for(int i=1;i<=n;i++) val[i]=Read();
for(int i=1;i<=n;i++) hgt[i]=Read();
for(int i=1;i<n;i++) Gr.AddEdge(Read(),Read());
ans=INF;
DP(1,0);
printf("%lld\n",ans);
return 0;
}

THE END

Thanks for reading!

> Linked 无人赞颂的旅程-网易云