题意：给你一张无向图，一开始携带有W元钱。走到x点，必须满足W>=Ax。可以选择在当前所在点捐献Bi的贡献（如果W<Bi，就不能做），并将此点标记。问标记完所有点，需要至少携带多少钱（最小W）？
n<=1e5。
标程：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int read() 5 { 6 int x=0,f=1;char ch=getchar(); 7 while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} 8 while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); 9 return x*f; 10 } 11 const int N=100005; 12 int cnt,head[N],a[N],b[N],id[N],u,v,fa[N],n,m,x,vis[N]; 13 ll f[N],bsum[N]; 14 struct node{int to,next;}num[N*2]; 15 void add(int x,int y) 16 {num[++cnt].to=y;num[cnt].next=head[x];head[x]=cnt;} 17 bool cmp(int A,int B) {return a[A]<a[B];} 18 int getfather(int x) {return fa[x]?fa[x]=getfather(fa[x]):x;} 19 int main() 20 { 21 n=read();m=read(); 22 for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(),a[i]=max(a[i]-b[i],0),id[i]=i; 23 for (int i=1;i<=m;i++) u=read(),v=read(),add(u,v),add(v,u); 24 sort(id+1,id+n+1,cmp); 25 for (int i=1;i<=n;i++) 26 { 27 x=id[i];vis[x]=1;f[x]=a[x];bsum[x]=b[x]; 28 for (int j=head[x];j;j=num[j].next) 29 if (vis[num[j].to]) 30 { 31 int y=getfather(num[j].to);//类似并查集找父亲，维护树形 32 if (x==y) continue; 33 fa[y]=x;bsum[x]+=bsum[y]; 34 f[x]=min(f[x],max(f[y],a[x]-bsum[y])); 35 } 36 } 37 printf("%lld ",bsum[id[n]]+f[id[n]]); 38 return 0; 39 }
题解：转换+性质神题
将限制合并成W-Bi>=max(Ai-Bi,0)。使得Ai=max（Ai-Bi，0）。
有结论：若Ax是当前的最大点，删去Ax后图被分成若干个连通块G1,G2,...,Gk。访问顺序G1,G2,...,Gk-1,x,Gk一定不劣。
[证明：如果先访问Gk中的某个点y，再访问x，由于Ax是当前最大，一定不会比先访问x后访问y的W答案来得小。]
因而，最后一次经过某个点时，我们把它捐掉。可以发现构成一棵树。有父亲的点捐完子树再往上走，没父亲的点捐完其他子树在最后一个子树中结束旅程。
在树上计算所需最小W，设bsum[i]为i子树中的B和。f[i]表示捐完当前子树所需的W比bsum[i]大多少。只用计算f[i]和最后经过的一个子树的不等式：1.W'>=Ai，即f[i]>=Ai-bsum[son]。W'表示捐完i点其他子树剩下的W，表示捐完其他子树后还能回到i点。2.W'>=bsum[son]+f[son]，即f[i]>=f[son]。表示可以进入son子树遍历。取所有子树中max(f[son],Ai-bsum[son])中最小的一个作为最后经过更新f[i]。
小细节：由于是在图上建树，用并查集维护父亲，每次找到一棵子树的根连接，避免信息遗漏。