# P8677 [蓝桥杯 2018 国 A] 采油 题解

· · 题解

P8677 [蓝桥杯 2018 国 A] 采油 题解

第一问

这一问是非常简单的，容易想到只要每条边只在从父节点走向子节点和从子节点走回父节点时被遍历，第一问的答案就是 \sum_{i=1}^{n-1} b_{i} \times2 ，即所有边权和的二倍。

第一问的主要用途其实是限制第二问的行动路径。

第二问

由第一问要求走最短路程，钻井的工作人员每进入一棵子树，就必须把该子树内所有油田都建上油井，才可离开此子树回到父节点。

发现了什么？每棵子树都可以当作子问题处理（类似树形 DP，将此子树化为一个“油田”。

我们只需要求出在每棵子树建造钻井需要花费的人力 B ，和此棵子树留下了多少人维护 S ，就可以实现。

转移过程考虑贪心。在两层之间，可以任意选择进入子树和在目前的根节点建立油井的顺序，我们要先在 B_{i}-S_{i} 较大的油田（或已 DP 的子树，可看作一个大“油田”）建油井，正确性从后面的递推式可以看出来。

接下来是贪心的实现过程，我使用的是递归（拓扑排序当然也可）。

先递归自己的每棵子树，将它化为一个“油田”，并将它们的 B 和 S 记到数组（我用的 vector）中，便于接下来排序。

for (int i=head[u];i;i=e[i].nex)
{   
       if (e[i].to==fa)    continue; //防止走回父节点
       func(e[i].to,u);
       a[u].push_back(a[e[i].to][0]);
}
sort(a[u].begin(),a[u].end(),cmp);

求值部分看代码，我定义了 C 表示 B-S，没有继续存 S ，你直接用 S 也可。

int ansb=0,nc=0; //ansb 表示处理到现在已经需要的人力，nc 表示目前剩余的人力
for (int i=0;i<a[u].size();i++)    //对于每个“油田”
{
    ansc+=a[u][i].b-a[u][i].c; //这里是为了求 ansc 作准备，可以忽略一会再看
    if(nc<a[u][i].b)  ansb+=a[u][i].b-nc,nc=a[u][i].c; //剩余人数不满足此油田要求，加人力
    else    nc-=a[u][i].b-a[u][i].c; //满足要求只需要留下人维护
}
ansc=ansb-ansc; //求真正的 ansc
a[u][0].b=ansb,a[u][0].c=ansc; //此子树处理完

注意

完整代码，不太优美

#include <bits/stdc++.h>
using namespace std;
#define N 100004
struct node{
    int b,s,c;
};
bool cmp(node x,node y){return x.c>y.c;}
struct edge{
    int to,nex;
}e[N<<1];
int head[N];
vector<node> a[N];
void func(int u,int fa)
{
    int ansc=0;
    for (int i=head[u];i;i=e[i].nex)
    {   
        if (e[i].to==fa)    continue;
        func(e[i].to,u);
        a[u].push_back(a[e[i].to][0]);
    }
    sort(a[u].begin(),a[u].end(),cmp);
    int ansb=0,nc=0;
    for (int i=0;i<a[u].size();i++)
    {
        ansc+=a[u][i].b-a[u][i].c;
        if(nc<a[u][i].b)  ansb+=a[u][i].b-nc,nc=a[u][i].c;
        else    nc-=a[u][i].b-a[u][i].c;
    }
    ansc=ansb-ansc;
    a[u][0].b=ansb,a[u][0].c=ansc;
    return;
}
signed main()
{
  int n;
  node tmp;
  cin>>n;
  for (int i=1;i<=n;i++) a[i].push_back(tmp),scanf("%d",&a[i][0].b);
  int mc=0,p;
  for (int i=1;i<=n;i++)
  {
    scanf("%d",&a[i][0].s);
    a[i][0].c=max(a[i][0].b-a[i][0].s,0);
    if(a[i][0].c>mc)mc=a[i][0].c>mc,p=i;
    a[i][0].b=max(a[i][0].b,a[i][0].s);
  }
 int nu,nv,nw,w=0;
 for (int i=1;i<=n-1;i++)
 {
    scanf("%d %d",&nv,&nw);
    w+=nw,nu=i+1;
    e[(i<<1)-1].to=nv,e[(i<<1)-1].nex=head[nu],head[nu]=(i<<1)-1;
    e[i<<1].to=nu,e[i<<1].nex=head[nv],head[nv]=i<<1;
 }
 cout<<w*2<<' ';
 func(p,0);
 cout<<a[p][0].b;
}