# Bzoj3252 攻略

Posted by yjjr's blog on February 6, 2018 1 minutes to read

Description

“为什么你还没玩就知道每个场景的价值呢？”

“我已经看到结局了。”

Input

Output

Sample Input

5 2

4 3 2 1 1

1 2

1 5

2 3

2 4

Sample Output

10

HINT

Source

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define v e[i].to
#define ll long long
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const  ll maxn=2e5+6;
struct edge{ll to,next;}e[maxn<<1];
#define v e[i].to
inline bool cmp(ll x,ll y){return x>y;}
void dfs(int x,int fa)
{
ll Max=0,mx;
reg(x)
{
if(v==fa)continue;
dfs(v,x);
if(w[v]>Max)Max=w[v],mx=v;
}
w[x]=Max+a[x];
reg(x)
{
if(v==fa||v==mx)continue;
c[++tot]=w[v];
}
}

int main()
{
rep(i,1,n-1){
}
tot=0;dfs(1,1);
c[++tot]=w[1];
sort(c+1,c+1+tot,cmp);
ll ans=0;
k=min(k,tot);
rep(i,1,k)ans+=c[i];
cout<<ans<<endl;
return 0;
}