E - Game 树上dfs贪心

佚名 6年前 (2019-05-07) 随笔 1777人围观抢沙发百度已收录

https://vjudge.net/contest/299785#problem/E

题意：给你n个点，n-1个边构成有向数，同时每个点都有一个权值，现在给你k次操作，每次操作你必须从根节点1出发，然后走到一个叶节点结束然后将它们点的权值累加，同时走过的点的权值不可以重复计算，问你k次之后最大得到多大的值。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

做法：我们倒着存边，两次dfs第一次求每个点到根节点的权值，然后将这个权值从大到小排序，第二次dfs贪心遍历每个从大到小排好序的节点，最后将得到的遍历结果再从大到小排序，取前k个数求和。

#include<bits/stdc++.h>
using namespace std; const int maxn=1e5+10; #define LL long long
struct note { LL id,val; } ye[maxn]; LL val[maxn]; LL sum[maxn],cnt; LL s[maxn]; vector<int> v[maxn]; LL dfs(int t) { if(sum[t]>0) return sum[t]; sum[t]=val[t]; for(int i=0; i<v[t].size(); i++) sum[t]+=dfs(v[t][i]); return sum[t]; } LL dfs1(int u) { if(sum[u]>0)return 0; sum[u]=val[u]; for(int i=0; i<v[u].size(); i++) { int x=v[u][i]; sum[u]+=dfs1(x); } return sum[u]; } bool cmp(note a,note b) { return a.val>b.val; } int main() { int t; scanf("%d",&t); for(int it=1; it<=t; it++) { int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) v[i].clear(); memset(sum,0,sizeof(sum)); memset(s,0,sizeof(s)); cnt=0; for(int i=1; i<=n; i++) scanf("%lld",&val[i]); for(int i=1; i<=n-1; i++) { int a,b; scanf("%d%d",&a,&b); v[b].push_back(a); } cnt=0; for(int i=1; i<=n; i++) { ye[++cnt].id=i; ye[cnt].val=dfs(i); } for(int i=1; i<=n; i++) { ye[i].id=i; ye[i].val=dfs(i); } sort(ye+1,ye+1+n,cmp); memset(sum,0,sizeof(sum)); for(int i=1; i<=n; i++) s[i]=dfs1(ye[i].id); LL ans=0; sort(s+1,s+1+n); for(int i=1; i<=m; i++) ans+=s[n-i+1]; printf("Case #%d: %lld\n",it,ans); } }