树锯结构~
# 题面
点击展开/折叠 题面
有一棵 $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
| #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; }
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 无人赞颂的旅程-网易云