一道感觉很神的题。
直觉是对的，但是仍然需要一些转化。
题目链接。
题意
现在有一张 个点 条边的无向联通图，每一个点有两个参数
。
初始时，你站在 ，身上有 元钱。
你可以沿着这张图的边任意移动，如果要移动到一个点 ，需要保证你身上至少有 元钱。
走到一个点 时，你可以选择捐增
元，需要保证此时你至少有 元。
你可以任意选择你的初始点，你现在要捐赠每一个点一次，求最小的 。
。
。
题解
看到这道题的 ，第一个想法就是重构树。
但是这个想法有一些问题。
例如，你现在在点 ，捐赠了 元钱，这个时候你的总钱数有可能比
要小，这不好办。
所以这道题想要使用重构树的话，还需要一些转化。
首先会发现一些奇妙的限制，例如捐赠一个点 的时候，一定是最后一次经过点 。
很显然，如果捐赠过后还经过了一次点 ，那么在这一次捐赠就很好了，中间一段拥有的钱还变多了，显然不劣。
这个时候，我们会发现一些神奇的事情，令 。
那么可以发现，任何时候，若你在
点，则你的剩余钱数一定 （无论捐赠前后）。
而且，若你此时的钱数 ，则一定可以满足
的限制。
这个是因为，如果你捐赠
点之后，如果还有 元，那么进入
点的时候，一定有
元。而你捐赠之后就不会再进入
点。
所以位于 点时钱数 与原题是等价的。
这个时候就可以使用重构树了。
对于一条边
来说，他的边权是 ，代表我们只有拥有这么多钱，才会走这条边。
然后我们对整张图找出最小生成树，那么我们一定只会走这棵树上的边。
接下来再来考虑如何计算答案。
考虑捐赠每一个点的顺序。
我们会发现，对于一棵子树，我们一定不会出现，先捐赠子树内的点，再捐赠子树外的点，最后再捐赠子树内的点的情况。
因为这棵子树的父亲的限制，一定不弱于这棵子树内所有的限制，所以我们先捐赠子树外点，最后再捐赠子树内点一定比上面那个方案更优。
有了这个结论，我们就可以跑树形 dp 了。
设 表示从
这个节点出发，捐赠完整棵子树，初始至少需要多少钱。
对于一个叶子节点 ，那么 。
对于非叶子节点 ，可以分类讨论先捐赠左子树点还是先捐赠右子树点，取较小的即可。
最终复杂度是 。
代码
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
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
struct node
{
int u,v,w;
}e[100001];
ll siz[200001];
ll dp[200001];
int fa[200001];
int ls[200001];
int rs[200001];
int a[100001];
int b[100001];
int c[200001];
int n,m,cnt;
inline int find(int num)
{
if(fa[num]==num) return num;
return fa[num]=find(fa[num]);
}
void dfs(int num)
{
if(num<=n)
{
siz[num]=b[num];
dp[num]=c[num]+b[num];
return ;
}
int u=ls[num],v=rs[num];
dfs(u),dfs(v);
siz[num]=siz[u]+siz[v];
ll vall=max(max(dp[u],c[num]+siz[u]),siz[u]+dp[v]);
ll valr=max(max(dp[v],c[num]+siz[v]),siz[v]+dp[u]);
dp[num]=min(vall,valr);
}
int main()
{
cnt=n=read(),m=read();
for(int i=1;i<=n;i++)
{
a[i]=read(),b[i]=read();
c[i]=max(a[i]-b[i],0);
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
e[i].u=read(),e[i].v=read();
e[i].w=max(c[e[i].u],c[e[i].v]);
}
sort(e+1,e+m+1,[](node a,node b){ return a.w<b.w;});
for(int i=1;i<=m;i++)
{
int u=find(e[i].u),v=find(e[i].v);
if(u==v) continue;
cnt++,ls[cnt]=u,rs[cnt]=v;
fa[cnt]=fa[u]=fa[v]=cnt;
c[cnt]=e[i].w;
}
dfs(cnt);
printf("%lld\n",dp[cnt]);
return 0;
}
|
感谢观看！