fork(2) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<utility>
  4. using namespace std;
  5.  
  6. #define VI vector<int>
  7. #define VII vector< vector<pair<int,int> > >
  8. #define MOD ( ((int)(1e9)+7) )
  9.  
  10. long long int dfs(int vertex,VII& adj,long long int& tweight)
  11. {
  12. 	int i;
  13. 	long long int rootCost = 0LL,childCost = 0LL,leafCost = 0LL; 
  14.  
  15. 	if( adj[vertex].size() == 0 )
  16. 		return 0LL;
  17.  
  18. 	for(i=0;i<adj[vertex].size();i++)
  19. 	{
  20. 		int adjNode = adj[vertex][i].first;
  21. 		int adjCost = adj[vertex][i].second;
  22.  
  23. 		leafCost = dfs(adjNode,adj,tweight);
  24.  
  25. 		tweight = ( tweight + leafCost ) % MOD;
  26. 		leafCost = ( leafCost * adjCost + adjCost ) % MOD;
  27.  
  28. 		rootCost = ( childCost * leafCost ) % MOD; /* Path that passes along the root */
  29. 		childCost = ( childCost + leafCost ) % MOD; /* Path that starts at the root and end at any child node */
  30.  
  31. 		tweight = ( tweight + rootCost ) % MOD;
  32. 	}
  33.  
  34. 	return childCost;
  35. }
  36.  
  37. int main()
  38. {
  39. 	std::ios_base::sync_with_stdio(false);
  40. 	int n,i,x,y,w;
  41. 	long long int tweight = 0LL;
  42. 	cin>>n;
  43.  
  44. 	VII adj(n+2);
  45.  
  46. 	for(i=1;i<=(n-1);i++)
  47. 	{
  48. 		cin>>x>>y>>w;
  49. 		if( x > y )
  50. 			std::swap(x,y);
  51. 		adj[x].push_back(make_pair(y,w));	
  52. 	}
  53. 	tweight = ( tweight + dfs(1,adj,tweight) ) % MOD; /* 1 will be the root always */
  54. 	cout<<tweight<<endl;
  55. }
  56.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
5 
1 5 2 
1 3 3 
1 4 2 
2 5 2
stdout
copy 
23
https://ideone.com/OVPROd
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!