CF1637F

CF1637F Towers

比较有意思的一个点是，我昨天给初一的神仙讲了两道换根（CF708C，uoj105），顺便总结了个套路。

然后今天早上打 VP 就遇到了 =_=

\(\text{Descrption}\)

You are given a tree which has \(n\) vertices with a height \(h\) on it.

You could put any numbers of tower on vertices, and you could choose the value of the tower \(e\).

If vertex \(x\) is on the path of \((u,v)\),and \(e_u,e_v\) satisfy \(\min(e_u,e_v) \ge h_x\), we call vertex \(x\) is good.

Your goal is to let all vertex become good vertex,and minumim your cost.

If you put a tower and its \(e=value\), then your total cost will be added \(value\).

\(\text{Solution}\)

首先我们可以发现一个结论，如果假定了树的根节点，那么每一个叶子节点都必须放一个 tower。

然后又可以发现一个结论，在假定了根节点的情况下，如果节点 \(u\) 是有信号的的，那么 \(u\) 的子树当中必然有至少一个 tower，满足这个 tower 的 \(e\ge h_u\) 。

上面的结论全部基于 “根节点假定” 的情况。

但是本题给出的明显是一颗无根树，所以我们很自然的想到了换根DP。

那么我们可以设 \(f_u\) 表示以 \(u\) 为根节点的时候，使每一个节点都变成有信号的节点的最小花费。

然后发现这个换根不是很好写。

又发现，如果让 \(h\) 最大的那一个（或者其中的一个）作为根节点，那么往下取值一定是最优的。

因为你现在要做的就是让每个子树当中都有一个 \(e\) 大于等于这个子树的根的 \(h\) 的 tower。

然后对于根节点，只需要让它的两个互不相同的子树当中有两个 tower 的 \(e=h_{root}\) 即可。

如果说这个 \(h\) 最大的点不是 \(root\) ，那么它就会在某个子树里面，就会导致子树里需要多放几个 \(e=h_{max}\) 的 tower，明显不是最优的。

所以我们就直接令这个 \(h\) 最大的点为 \(root\) ，然后递归下去处理就行了。

\(\text{Code}\)

实现

#include<bits/stdc++.h>
using namespace std;

#define int long long
constexpr int inf=1e18+1,si=2e5+10;
int n,height[si],res;
struct Edge{
    int head,ver,Next;
}e[si<<1]; int tot=0,root=0,rt[si];
inline void add(int u,int v){ e[++tot].ver=v,e[tot].Next=e[u].head,e[u].head=tot; }
inline pair<int,int> dfs(int u,int fa){
    int max1,max2; max1=max2=0;
    for(register int i=e[u].head;i;i=e[i].Next){
        int v=e[i].ver; if(v==fa) continue;
        int now=dfs(v,u).first; if(now>max1) max2=max(max2,max1),max1=now; else max2=max(max2,now);
    } if(fa!=0) res+=max(height[u]-max1,0ll),max1+=max(height[u]-max1,0ll);
    else res+=max(height[u]-max1,0ll)+max(height[u]-max2,0ll); return make_pair(max1,max2);
}
signed main(){
    scanf("%lld",&n); for(register int i=1;i<=n;++i) scanf("%lld",&height[i]);
    for(register int i=1,u,v;i<n;++i) scanf("%lld%lld",&u,&v),add(u,v),add(v,u);
    for(register int i=1;i<=n;++i) root=height[i]>height[root]?i:root; dfs(root,0); return printf("%lld\n",res),0;   // 
}

Tag : 树/树形DP/换根DP

---

最后更新: May 9, 2023