hdu 5242 Game 题解（贪心，树链剖分思想）

原题链接： HDU：点我QωQ

题意简述

多组数据。 给定一棵树，带点权，请你遍历$k$次，遍历过两次的点权值只算一次，权值和最大。

数据

输入

第一行一个$T$，表示有$T$组数据。($T<=20$)接下来，每组数据开头有一个$n$，表示树上有$n$个点。（$n<=10^5$） 下来一行有$n$个数，表示点$1...n$的点权。(非负，在$int$内） 接下来$n-1$行，每行一个$a,b$，表示$a$是$b$的父节点。（$1<=a,b<=n$）

输出

$T$行，对于第$i$组数据，输出"$Case(空格)\#i:(空格)答案$"。

样例

输入 2 5 2 4 3 2 1 1 1 2 1 5 2 3 2 4 5 3 4 3 2 1 1 1 2 1 5 2 3 2 4 输出 Case #1: 10 Case #2: 11

思路

我们拿树链剖分的思想去看这个题。经过两次只加一次点权，但是路径会不一样。显然，一次遍历必须遍历到叶子，要不然就亏了（点权非负）。而且一次遍历不珂能遍历到两个或以上的叶子，所以，我们遍历$k$次，就相当于$选k个叶子到根$。 那么，我们选哪些呢？ 贪心选择。先$DFS$求出所有点到根路径的权值和。我们按这个值从大到小排序，再依次$DFS$求出不重复的权值和（反向建图，搜回根即珂），取前$k$大加起来即珂。正确性。。。自己模拟一下就知道了。给一个稍微有点强度的数据（我自己就是用这个理解的）： 输入：

1 7 2 0 3 1 1 2 1 1000 1 2 1 3 3 4 4 5 5 6 4 7

输出：1005

代码:

#include<bits/stdc++.h> using namespace std; namespace Flandle_Scarlet { #define N 100100 #define int long long vector<int>g[N],ig[N]; //图,反图 int n,k; int w[N]; struct node { int ans; int id; }a[N];bool operator<(node x,node y){return x.ans>y.ans;} //一个节点的编号，答案 void Input() { scanf("%lld%lld",&n,&k); for(int i=1;i<=n;++i) { scanf("%lld",&w[i]); a[i].id=i; a[i].ans=w[i]; } for(int i=1;i<n;++i) { int a,b; scanf("%lld%lld",&a,&b); g[a].push_back(b); ig[b].push_back(a);//正反建图 } } void DFS1(int u) { for(int v:g[u]) { a[v].ans+=a[u].ans;//处理路径点权和 DFS1(v); } } bool vis[N]; int DFS2(int u,int val) { if (u==1 and !vis[u])//搜到根了,而且没访问过 { vis[u]=1; return w[u]; } if (u==1 or vis[u]==1) return 0;//该回去的两种情况 vis[u]=1; for(int v:ig[u])//反着回去 { if (vis[v]==1) return val; else return val+DFS2(v,w[v]); } } void Solve(int Case) { DFS1(1); sort(a+1,a+n+1);//先处理出权值和,排序 for(int i=1;i<=n;++i) { a[i].ans=DFS2(a[i].id,w[a[i].id]); }//新的答案 sort(a+1,a+n+1); int ans=0; for(int i=1;i<=k;++i) { ans+=a[i].ans; }//取前k大加起来 printf("Case #%lld: %lld\n",Case,ans); } void InitAll() { //variables n=k=0; //arrays memset(vis,0,sizeof(vis)); memset(w,0,sizeof(w)); for(int i=0;i<N;++i) { g[i].clear(); ig[i].clear(); } } void Main() { if (0) { freopen("","r",stdin); freopen("","w",stdout); } int t;scanf("%lld",&t); for(int i=1;i<=t;++i) { InitAll(); Input(); Solve(i); } } #undef N //100100 #undef int //long long }; int main() { Flandle_Scarlet::Main(); return 0; }

回到总题解界面