题解 AT4144 【[ARC098D] Donation】
command_block
2021-01-12 18:54:56
**题意** ： 给出一张 $n$ 个点 $m$ 条边的无向连通图。
点 $u$ 有两参数 $A_u,B_u$。当你经过该点时，必须至少拥有 $A_u$ 元，在该点打卡需要花费 $B_u$ 元。
你可以从任意点开始旅程。你需要在所有点打卡一次，问初始时最少需要携带多少元。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
很有意思的一个题。
- **性质** ： 在某点打卡后必不会再次访问某点。
**解释** ：不难发现，旅行中的钱数是单调不增的。
若两次访问某点，第一次不打卡，第二次打卡要比第一次就打卡优，因为中间的一段路程余钱更多。
若遵守上述策略，令 $C_u=\max(A_u-B_u,0)$ ，约束可以等价于 ： 在 $u$ 点的所有时刻钱数都 $\geq C_u$。
一种直观的想法是 ： 按照 $C$ 排序，并按顺序打卡。
可惜的是，在点之间移动时，受到图的限制，途中可能经过 $C$ 更大的节点。
我们将 $u\rightarrow v$ 的边权设为 $\max(C_u,C_v)$ ，求最小生成树，不难发现最优的移动路径只会在最小生成树上，这样就把图简化成了树。
最小生成树的性质仍然不够好（边上的 $C$ 是乱序的），考虑建立重构树。
观察边权的性质，根据 $\rm Kruskal$ ，建树的过程等价于按照 $C$ 从小到大枚举点 $u$ ，然后尽量加入和 $C$ 更小的点 $v$ 连接的边。
我们连边 （$u\rightarrow v$ 目前的最浅祖先）。这样就建立了类似重构树的结构，满足下面两条关键性质 ：
- 深度越深， $C$ 越小。
- 两点间路径的 $\max C$ 取得最小值。
接下来在树上 $\rm DP$。
设 $dp[u]$ 为处理完 $u$ 子树（不必回到 $u$）所需的初始钱数，$s[u]$ 为子树内 $B$ 的和。
对于叶节点，显然有 $dp[u]=B_u+C_u$。
对于非叶节点，若有 $k$ 个子树，要先处理 $k-1$ 个，然后在 $u$ 打卡，然后处理最后一个。
在处理前面 $k-1$ 个时，由于树中的 $C$ 上大下小，而钱单调不增，所以只需要考虑在 $u$ 打卡的一次约束。
枚举最后进入的子树 $v$ ，则有 $dp[u]=\min\limits_{u\rightarrow v}(s[u]-s[v]+\max(C_u,dp[v]))$
其中，$s[u]-s[v]$ 是处理前面 $k-1$ 个子树的花费，$\max(C_u,dp[v])$ 是后面的限制。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 105000
using namespace std;
struct UFS{
int f[MaxN];
void Init(int n)
{for (int i=1;i<=n;i++)f[i]=i;}
int find(int u)
{return f[u]==u ? u : f[u]=find(f[u]);}
bool merge(int u,int v){
u=find(u);v=find(v);
if (u==v)return 0;
f[u]=v;return 1;
}
}F;
vector<int> g[MaxN],org[MaxN];
ll dp[MaxN],s[MaxN];
int c[MaxN],b[MaxN];
void pfs(int u)
{
s[u]=b[u];
for (int i=0;i<g[u].size();i++){
pfs(g[u][i]);
s[u]+=s[g[u][i]];
}
}
void dfs(int u)
{
if (!g[u].size())dp[u]=b[u]+c[u];
else dp[u]=1ll<<60;
for (int i=0,v;i<g[u].size();i++){
dfs(v=g[u][i]);
dp[u]=min(dp[u],s[u]-s[v]+max((ll)c[u],dp[v]));
}
}
bool cmp(int A,int B)
{return c[A]<c[B];}
int n,m,p[MaxN];bool vis[MaxN];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d%d",&c[i],&b[i]);
c[p[i]=i]=max(c[i]-b[i],0);
}for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
org[u].pb(v);org[v].pb(u);
}
sort(p+1,p+n+1,cmp);
F.Init(n);
for (int t=1;t<=n;t++){
int u=p[t];
for (int i=0,v;i<org[u].size();i++)
if (vis[v=org[u][i]]){
v=F.find(v);
if (F.merge(v,u))g[u].pb(v);
}
vis[u]=1;
}
pfs(p[n]);dfs(p[n]);
printf("%lld",dp[p[n]]);
return 0;
}
```