admin管理员组文章数量:1609209
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
using namespace std;
#define X first
#define Y second
#define eps 1e-2
#define gcd __gcd
#define pb push_back
#define PI acos(-1.0)
#define lowbit(x) (x)&(-x)
#define bug printf("!!!!!\n");
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef unsigned long long uLL;
const int N = 1e5+2;
const int INF = 1<<30;
const int mod = 1e9+7;
#define int long long
int n,k;
std::vector<pair<int,int> > g[N];
int dp[N][2];
bool cmp(pair<int,int> a,pair<int,int> b){
if(a.first==b.first) return a.second<b.second;
return a.first>b.first;
}
vector< pair<int,int> > tk[N];
void dfs(int x,int fa){
for(int i=0;i<g[x].size();i++){
int to=g[x][i].first;
if(to==fa) continue;
dfs(to,x);
tk[x].push_back({dp[to][0]+g[x][i].second,to});
}
sort(tk[x].begin(),tk[x].end(),cmp);
int sum=0;
for(int i=0;i<tk[x].size();i++){
sum+=tk[x][i].first;
if(i>=k-1) break;
}
for(int i=0;i<tk[x].size();i++){
dp[x][0]+=tk[x][i].first;
if(i>=k-2) break;
}
for(int i=0;i<tk[x].size();i++){
if(i>k-1) break;
int to=tk[x][i].second;
dp[x][1]=max(dp[x][1],sum-dp[to][0]+dp[to][1]);
}
}
void solve(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<n;i++){
int v,u,val;
scanf("%lld%lld%lld",&v,&u,&val);
++v,++u;
g[v].push_back({u,val});
g[u].push_back({v,val});
}
dfs(1,-1);
cout<<dp[1][1]<<endl;
return;
}
int32_t main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
int t = 1;
//scanf("%d",&t);
while(t--){
// printf("Case %d: ",cas++);
solve();
}
return 0;
}
本文标签: OnlinemirrorHelveticcodingContest
版权声明:本文标题:Helvetic Coding Contest 2017 online mirror (teams allowed, unrated) K - Send the Fool Further! (medi 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728549752a1163277.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论