Tietoverkko

#include <iostream>
#include <map>
#include <bits/stdc++.h>
using namespace std;
using std::map;


map<long,long> *koneet;
long total = 0;
long tries = 0;

map<long,long> Crossroads(long kone,long source,long sourceSpeed) {
	tries+=1;
	//if (tries>300){cout << "x";return yhteydet;}
	
	map<long,long> &ko = koneet[kone];
	long haaSize = ko.size()-1;
	
	if(haaSize==0){
	
		//return map<long,long> {{sourceSpeed,1}};
		map<long,long> a;
		a[sourceSpeed]=1;
		return a;
	}
	
	if (source==0){
		haaSize+=1;
	}
	
	vector<map<long,long>> haarat(haaSize+1);  //=new map<long,long>[haaSize+1];
	long i_k = 0;
	for (auto &item : ko){
		if (item.first !=source){
			haarat[i_k]=Crossroads(item.first,kone,item.second);
			//delete koneet[item.first];
			i_k+=1;
		}
	}
	long addTotalHalf = 0;
	map<long,long> yhteydet;
	yhteydet[sourceSpeed] = 1;
	
	//for (long i = 0; i<haaSize; i++){
	for (auto &item1 : haarat){
		for (auto &item : item1){
			long a = std::min(item.first, sourceSpeed);
			yhteydet.emplace(a,0);
			yhteydet[a]+=item.second;
			addTotalHalf+=2*item.second*item.first;
		}
	}
	
	if (haaSize>1){
		//long addTotalHalf = 0;
		map<long,long> yhtyhaara;
		
		//for (long i = 0; i<haaSize; i++){
		for (auto &item1 : haarat){
			for (auto &item : item1){
				yhtyhaara.emplace(item.first,0);
				yhtyhaara[item.first]+=item.second;
			}
		}
		//long yhSize = yhtyhaara.size();

		long ta = 0;
		long tb = 0;
		for (auto &item : yhtyhaara){
			tb+=item.second;
		}
		for (auto &item : yhtyhaara){
			ta+=item.first*item.second;
			tb-=item.second;
			addTotalHalf+=(ta+tb*item.first)*item.second;
		}
		for (auto &item1 : haarat){
			long ta = 0;
			long tb = 0;
			for (auto &item : item1){
				tb+=item.second;
			}
			for (auto &item : item1){
				ta+=item.first*item.second;
				tb-=item.second;
				addTotalHalf-=(ta+tb*item.first)*item.second;
			}
		}
		//addTotal+=addTotalHalf/2;
		}
	
	total+=addTotalHalf;
	//delete[] haarat;
	return yhteydet;
}

int main(){
	long n;
	cin >> n;
	koneet =new map<long,long>[n+1];
	for (long i = 0; i<n; i++){
		long c0,c1,c2;
		cin >> c0 >> c1 >> c2;
		koneet[c0][c1]=c2;
		koneet[c1][c0]=c2;
	}

	Crossroads(1,0,0);
	cout << total/2;

    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED