Submission #914667

---

Source Code Expand

#include<bits/stdc++.h>
#define reps(i,j,k) for(int i=(j);i<(k);++i)
#define rep(i,j) reps(i,0,j)
#define pb push_back
#define fs first
#define sc second
#define mk make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;

template<class T>
ostream &operator<<(ostream &out, const vector<T> &v){
	out << "{";
	rep(i,v.size())
		out << v[i] << ", ";
	return out << "}" << endl;
}

template<class S, class T>
ostream &operator<<(ostream &out, const pair<S,T> p){
	return out << "(" << p.fs << ", " << p.sc << ")";
}



class Node{
public:
	int cost;
	vector<pii> edge;//to, dist
	Node(){}
	
};

int reach[2001];
vector<ll> u;
vector<Node> v;

vi dfs(int current, int dist){
	reach[current] = 1;
	vi dists;
	ll maxdist = 0;
	rep(i,v[current].edge.size()){
		pii t = v[current].edge[i];
		if(reach[t.fs]) continue;
		vi tmp = dfs(t.fs, t.sc);
		rep(j,tmp.size()){
			dists.pb(tmp[j]);
			if(maxdist < tmp[j]){
				maxdist = tmp[j];
			}
		}
	}
	//sort(dists.rbegin(),dists.rend());
	if(dists.size()!=0){ 
		rep(i,dists.size()) if(dists[i] == maxdist) {
			dists[i] += dist;
			break;
		}
	}
	else dists.pb(dist);
//	cout << "dfs; " << current << ": " << dists;
	return dists;
}

int main(){
	int n,m;
	cin >> n >> m;
	v.resize(n+1);
	rep(i,n-1){
		int a, b, c;
		cin >> a >> b >> c;
		v[a].edge.pb(pii(b,c));
		v[b].edge.pb(pii(a,c));
	}

	rep(i,n)
		cin >> v[i+1].cost;
	
	vector<ll> u;

	reps(i,1,
	//	2){
		n+1){
		fill(reach, reach+2001, 0);
		
		vi tmp = dfs(i,0);
	//	if(i==1){
	//		cout << i << endl;
	//		cout << tmp;
	//	}
		rep(j,tmp.size())u.pb(tmp[j] * v[i].cost);
	}
	sort(u.rbegin(),u.rend());
	ll ans =0;
	rep(i,min(m,(int)u.size())) ans += u[i];
	cout << ans << endl;	
	//cout << u;
	return 0;
}

Submission Info

Judge Result