题解 P6943【[ICPC2018 WF]Conquer The World】
Verdandi
2021-11-08 16:12:11
[P6943 [ICPC2018 WF]Conquer The World](https://www.luogu.com.cn/problem/P6943)解题报告：
[更好的阅读体验](https://www.cnblogs.com/xiaoziyao/p/15524172.html)
## 题意
给定一个 $n$ 个点的带点边权的树（设点权为 $v$），可以任意将点的点权在树上进行移动，移动单位点权的代价为路径上的边权和，求让所有点点权非负的最小代价。
$1\leqslant n\leqslant 2.5\times 10^5,\sum v\geqslant 0,\sum[v>0]v\leqslant 10^6$
## 分析
小清新题。
下面称正点权点为源，负点权点为汇。
首先有一个明显的费用流做法，直接源点连正点权，负点权连汇点然后费用流即可。
我们可以发现一个性质，对于匹配的两条路径，它们交叉的代价一定不优于它们不交叉的代价。
于是可以考虑反悔贪心（模拟费用流），设当前子树的根为 $x$，那么：
贪心策略：每次找到深度最小的源和深度最小的汇进行匹配。
反悔策略：将源的点权改成 $2dep_x$ 减去汇的点权，将汇的点权改成 $2dep_x-$ 减去源的点权即可，容易发现这样匹配之后可以取消掉这对源汇的匹配。
使用左偏树来支持堆的合并即可，时间复杂度 $O(\sum|v|\log(\sum|v|))$。
## 代码
直接用了 pbds 来实现左偏树。
[AC 记录](https://www.luogu.com.cn/record/62047327)
```
#include<stdio.h>
#include<vector>
#include<ext/pb_ds/priority_queue.hpp>
#define inf 1000000000000
using namespace std;
const int maxn=250005;
int n,tot;
int a[maxn],b[maxn];
long long ans;
long long dep[maxn];
vector< pair<int,int> >v[maxn];
__gnu_pbds::priority_queue< long long,greater<long long> >A[maxn],B[maxn];
void dfs(int x,int last){
for(int i=a[x]+1;i<=b[x];i++)
A[x].push(dep[x]-inf),tot++;
for(int i=b[x]+1;i<=a[x];i++)
B[x].push(dep[x]);
for(int i=0;i<v[x].size();i++){
int y=v[x][i].first,z=v[x][i].second;
if(y!=last)
dep[y]=dep[x]+z,dfs(y,x),A[x].join(A[y]),B[x].join(B[y]);
}
while(!A[x].empty()&&!B[x].empty()&&A[x].top()+B[x].top()-2*dep[x]<0){
long long u=A[x].top(),v=B[x].top();
A[x].pop(),B[x].pop(),ans+=u+v-2*dep[x];
A[x].push(2*dep[x]-v),B[x].push(2*dep[x]-u);
}
}
int main(){
scanf("%d",&n);
for(int i=1,x,y,z;i<n;i++)
scanf("%d%d%d",&x,&y,&z),v[x].push_back(make_pair(y,z)),v[y].push_back(make_pair(x,z));
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
dfs(1,0);
printf("%lld\n",ans+1ll*tot*inf);
return 0;
}
```