Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <set>
- #include <map>
- #include <cmath>
- #include <time.h>
- #include <vector>
- #include <string>
- #include <cstdio>
- #include <cstring>
- #include <cassert>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define ll long long
- #define ld long double
- const int MAXN = 11000;
- struct Edge{
- int u, v, l;
- };
- int n;
- Edge e[MAXN];
- vector<int> g[MAXN];
- int dfs(int u, int par){
- int res = 1;
- for (int i = 0; i < g[u].size(); i++){
- int v = (e[g[u][i]].u == u ? e[g[u][i]].v : e[g[u][i]].u);
- if (v != par) res += dfs(v, u);
- }
- return res;
- }
- int main(){
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen("bridges.in", "r", stdin);
- freopen("bridges.out", "w", stdout);
- #endif
- int k, sh, sc;
- cin >> n >> k >> sh >> sc;
- for (int i = 0; i < n - 1; i++){
- cin >> e[i].u >> e[i].v >> e[i].l;
- e[i].u--, e[i].v--;
- g[e[i].u].push_back(i);
- g[e[i].v].push_back(i);
- }
- vector<pair<ll, int> > v;
- for (int i = 0; i < n - 1; i++){
- int inleft = dfs(e[i].u, e[i].v);
- v.push_back(make_pair((ll)inleft * (n - inleft) * e[i].l, i));
- }
- sort(v.begin(), v.end());
- if (sh < sc) reverse(v.begin(), v.end());
- for (int i = 0; i < k; i++)
- cout << v[i].second + 1 << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement