Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define mp make_pair
- #define pb push_back
- #define INF 0x3f3f3f3f
- #define LINF 0x3f3f3f3f3f3f3f3fLL
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef set<int> si;
- typedef pair<int,int> ii;
- typedef vector<ii> vii;
- typedef map<string,int> msi;
- typedef map<int,int> mi;
- class UnionFind{
- public:
- vector<int>p,rank;
- UnionFind(int n){
- p.resize(n);
- rank.assign(n,0);
- for(int i=0;i<n;i++){
- p[i]=i;
- }
- }
- int findSet(int i){
- if(p[i] == i) return i;
- return (p[i] = findSet(p[i]));
- }
- bool isSameSet(int i,int j){
- return findSet(i) == findSet(j);
- }
- void unionSet(int i, int j){
- if(isSameSet(i,j)) return;
- int x = findSet(i);
- int y = findSet(j);
- if(rank[x] > rank[y]){
- p[y] = x;
- return;
- }
- p[x] = y;
- if(rank[x] == rank[y]) rank[y]++;
- }
- };
- struct aresta
- {
- int a,b,c;
- aresta(int x,int y,int z){
- a = x;
- b = y;
- c = z;
- }
- bool operator<(const aresta o) const{
- return c < o.c;
- }
- };
- int main(){
- while(!cin.eof()){
- int n;
- cin >> n;
- //cout <<"-" <<n<<endl;
- vector<aresta> a;
- UnionFind uf(n+1);
- for(int i =1;i<n;i++){
- int k;
- cin >> k;
- //cout << k;
- while(k--){
- int j,c;
- cin >> j>>c;
- //cout << " "<< j<< " "<<c;
- a.pb(aresta(i,j,c));
- }
- //cout << '\n';
- }
- sort(a.begin(),a.end());
- ll custo =0;
- for(int i=0;i<a.size();i++){
- if(!uf.isSameSet(a[i].a,a[i].b)){
- uf.unionSet(a[i].a,a[i].b);
- custo+=a[i].c;
- }
- }
- map<int,int> cont;
- for(int i=1;i<=n;i++){
- cont[uf.p[i]]++;
- }
- cout<< cont.size() << ' '<<custo<<'\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement