Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5 + 10;
- const ll INF = 1e18;
- int n, k;
- vector<pair<int, int> > graph[maxn];
- bool pay_toll[maxn];
- pair<ll, ll> dfs(int node, int parent) {
- ll res = 0, sum = 0, max_edge = 0;
- for(int i = 0; i < (int) graph[node].size(); i++) {
- int neighbour = graph[node][i].first;
- if(neighbour != parent) {
- ll weight = graph[node][i].second;
- pair<ll, ll> p = dfs(neighbour, node);
- res += p.first;
- sum += min(weight, p.second);
- max_edge = max(max_edge, min(weight, p.second));
- }
- }
- if(pay_toll[node]) {
- res += sum;
- max_edge = INF;
- }
- else {
- res += sum - max_edge;
- }
- return make_pair(res, max_edge);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin >> n >> k;
- for(int i = 1; i < n; i++) {
- int a, b, c;
- cin >> a >> b >> c;
- graph[a].push_back(make_pair(b, c));
- graph[b].push_back(make_pair(a, c));
- }
- for(int i = 0; i < maxn; i++) {
- pay_toll[i] = false;
- }
- for(int i = 0; i < k; i++) {
- int x;
- cin >> x;
- pay_toll[x] = true;
- }
- cout << dfs(0, -1).first << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement