Groundhog and Apple Tree
题目大意
给一棵树,有边权,点权。
走过这条边的需要的hp是边权。只有hp大于等于边权的时候才能走这条边。
第一次走到这个点可以获得 ai 的hp。
也可以呆在原地不动休息,每秒hp增加1。
刚开始在1号节点,问要走完所有的点,并且回到一号节点所需要的最少的休息时间。
题解
首先,这个题肯定是考虑子树走的顺序。
因为如果走完这颗子树,可以额外获得一些 hp 在走下一棵子树的时候就会抵消掉一些,少一点等待时间。
于是,考虑怎么贪心的走。
好了,比赛的时候就到这里,不会贪心。。脑子一片混乱。感觉这个题好乱,但是看了大佬的题解之后就感觉很清晰了。
定义,需要等待的时间为花费,走完这颗子树所获得的hp为贡献。
对于一个点,如果这个点的花费小于贡献,肯定先走这个点。
因为获得的贡献大的话就可以抵消掉后面的。
然后花费小于贡献的肯定先走,花费大于贡献的肯定后走。
把这两块分开讨论。
花费小于贡献的点:
肯定先走花费小的点,因为如果先走花费大的话,可能造成他的贡献后面小的用不完,但是后面走花费大的话,就可以用前面的子树的贡献。
也就是花费尽量用前面的贡献来填上,所以肯定是先走花费小的。
花费大于贡献的点
如果两个子树:
花费为 x1 , x2 贡献为 y1 , y2
如果先走1这颗子树:花费是 ans1 = x1 + x2 - y1
先走2这颗子树:花费是:ans2 = x2 + x1 - y2 .
当ans1 < ans2 的时候 y1 > y2 。
所以先走贡献大的点。
实现的话,dfs后序里面sort排个序就好了
官方题解不是这样的,本菜鸡看不懂
代码:
#include<algorithm>
#include<iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){
freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
a %= mod;ll ans = 1;while(b > 0){
if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
bool operator()(const pii & a, const pii & b){
return a.second < b.second;}};
int lb(int x){
return x & -x;}
//friend bool operator < (Node a,Node b) 重载
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1e9+7;
const int maxn = 1e5+10;
const int M = 5e3;
std::vector<pii> vv[maxn];
ll hua[maxn];//hua费
ll de[maxn];//得到的
std::vector<pll> temp, pp;
bool cmp(pll x,pll y)
{
return x.sd < y.sd;
}
bool cmp2(pll x,pll y)
{
return x.st > y.st;
}
int a[maxn];
void dfs(int x,int fa)
{
for (int i =0 ; i < vv[x].size(); i ++ )
{
int v = vv[x][i].st;
if(v == fa)
continue;
dfs(v,x);
}
temp.clear();
pp.clear();
// st 得到的 sd 花费的
for (int i = 0; i < vv[x].size(); i ++ )
{
int v = vv[x][i].st;
if(v == fa)
continue;
hua[v] += vv[x][i].sd;
if(de[v] > vv[x][i].sd)
{
de[v] -= vv[x][i].sd;
}
else
{
hua[v] += vv[x][i].sd - de[v];
de[v] = 0;
}
if(de[v] >= hua[v])
temp.pb(mkp(de[v],hua[v]));
else
pp.pb(mkp(de[v],hua[v]));
}
sort(temp.begin(),temp.end(),cmp);
ll h = 0, d = a[x];
for (int i =0 ; i < temp.size(); i ++ )
{
ll minn = min(temp[i].sd, d);
temp[i].sd -= minn;
d -= minn;
h += temp[i].sd;
d += temp[i].st;
}
sort(pp.begin(),pp.end(), cmp2);
for (int i =0 ; i < pp.size(); i ++ )
{
ll minn = min(pp[i].sd, d);
pp[i].sd -= minn;
d -= minn;
h += pp[i].sd;
d += pp[i].st;
}
hua[x] = h;
de[x] = d;
}
int main()
{
int T;
scanf("%d",&T);
while(T -- )
{
int n;
scanf("%d",&n);
for (int i= 1; i <= n; i ++ )
{
vv[i].clear();
hua[i] = 0;
de[i] = 0;
}
for (int i= 1; i <= n; i ++ )
scanf("%d",&a[i]);
for (int i = 1; i < n; i ++ )
{
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
vv[x].pb(mkp(y,v));
vv[y].pb(mkp(x,v));
}
dfs(1,0);
printf("%lld\n",hua[1]);
}
}
我好菜~~想了好久没想出来。