概要

比赛地址

2020牛客暑期多校训练营（第九场）

题目

A

B. Groundhog and Apple Tree

题目大意

给你一棵树，每个节点有个权值 w_i ，且每条边有个权值 c_i ，一个人从一号节点开始可以往另外一个节点爬，通过一条边需要消耗 c_i 的体力，爬到一个节点可以获得 w_i 的体力。每条边只能爬两次，且每个节点只能获取一次体力。且每休息一单位时间可以获取一点体力，最终要爬回1号节点，问每个节点都访问一遍的休息时间最少是多少。

解题思路

树上dp+贪心

每个节点保存两个值，一个是最少消耗的时间 cost_i 和返回后的收益 c_i 对每个节点的儿子考虑贪心，若其返回收益 c大于0，则按每个儿子的 cost 递增排序，否则按 cost+c 排序。然后计算当前节点的 cost 和 c 即可，返回时需要计算回去时的消耗和来的时候的消耗即可。最终答案就是 cost_1 。

AC代码

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,long long>
#define x first
#define y second
using namespace std;
const int maxn=1e5+10;
vector<pii> v[maxn];
int n;
ll a[maxn],c[maxn],b[maxn];
ll cost[maxn];
bool cmp(pii x,pii y)
{
    if(c[x.x]>=0)
    {
        if(c[y.x]<0) return 1;
        else if(cost[x.x]<cost[y.x]) return 1;
        else return 0;
    }
    else 
    {
        if(c[y.x]>=0) return 0;
        return cost[x.x]+c[x.x]>cost[y.x]+c[y.x];
    }
}
void dfs(int x,int fa)
{
    for(pii i:v[x])
    {
        if(i.x==fa) continue;
        b[i.x]=i.y;
        cost[i.x]+=i.y;
        dfs(i.x,x);
    }
    sort(v[x].begin(),v[x].end(),cmp);
    ll now=a[x];
    for(pii i:v[x])
    {
        if(i.x==fa) continue;
        if(now<cost[i.x]) cost[x]+=cost[i.x]-now,now=cost[i.x];
        now=now+c[i.x];
    }
 //   printf("p=%d %lld %lld\n",x,c[x],cost[x]);
    if(now<b[x]) cost[x]+=b[x]-now,now=b[x];
    now-=b[x];
    c[x]=now-cost[x];
  //  printf("t=%d %lld %lld\n",x,c[x],cost[x]);
}
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1,x,y;i<n;i++)
    {
        ll z;
        scanf("%d%d%lld",&x,&y,&z);
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    dfs(1,0);
    printf("%lld\n",cost[1]);
    for(int i=1;i<=n;i++) a[i]=c[i]=cost[i]=b[i]=0,v[i].clear();
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

总结

场上 now 的值没开ll，然后wawa大哭。

C

D

E

F

G

H

I

J

K

L