fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. # define C continue;
  5. # define R return
  6.  
  7. # define D double
  8. # define I insert
  9. # define ll long long
  10. # define ld long double
  11.  
  12. # define ull unsigned long long
  13. # define ui unsigned int
  14.  
  15. # define pb push_back
  16. # define pf push_front
  17.  
  18. # define vi vector < int >
  19. # define vc vector < char >
  20. # define vs vector < string >
  21. # define vb vector < bool >
  22. # define vd vector < D >
  23. # define vll vector < ll >
  24. # define vull vector < ull >
  25. # define vld vector < ld >
  26. # define PQ priority_queue
  27.  
  28. # define vvi vector < vector < int > >
  29. # define vvb vector < vector < bool > >
  30. # define vvc vector < vector < char > >
  31. # define vvll vector < vector < ll > >
  32. # define vvd vector < vector < D > >
  33. # define vvld vector < vector < ld > >
  34.  
  35. # define all(v) (v).begin() , (v).end()
  36. # define allrev(v) (v).rbegin() , (v).rend()
  37. # define allcomp(v) v.begin() , v.end() , comp
  38. # define allrevcomp(v) v.rbegin() , v.rend() , comp
  39.  
  40. # define pii pair < int , int >
  41. # define pll pair < ll , ll >
  42. # define pld pair < ld , ld >
  43. # define pDD pair < D , D >
  44.  
  45. # define vpld vector < pld >
  46. # define vpii vector < pii >
  47. # define vpll vector < pll >
  48. # define vpDD vector < pDD >
  49.  
  50. # define vvpii vector < vector < pii > >
  51. # define F first
  52. # define S second
  53. # define mp make_pair
  54.  
  55. # define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))
  56.  
  57. # define pp(n) printf("%.10Lf",n);
  58. # define line cout<<"\n";
  59. # define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
  60.  
  61. string vow = "aeiou";
  62. int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  63.  
  64. const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
  65. const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};
  66.  
  67. const int dx[] = { -1 , 0 , 0 , 1 } ;
  68. const int dy[] = { 0 , -1 , 1 , 0 } ;
  69.  
  70. const ld pie = 3.1415926535897932384626 ;
  71. const ll mod = 1e9 + 7 ;
  72.  
  73. /// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b ) .
  74.  
  75. const int N = 5e3 + 3 , inf = 1e6 + 2 ;
  76.  
  77. vpii g[N] ;
  78. int ans[N] ;
  79.  
  80. bool vis[N] ;
  81.  
  82. int n ;
  83.  
  84. void bad()
  85. {
  86. 	cout << -1 ;
  87. 	line ; exit ( 0 ) ;
  88. }
  89.  
  90. void read()
  91. {
  92. 	cin >> n ;
  93. 	int m = n - 1 ;
  94.  
  95. 	for ( int i=0 ; i < m ; i ++ )
  96. 	{
  97. 		int a , b ;
  98. 		cin >> a >> b ;
  99.  
  100. 		a -- ; b -- ;
  101.         g[a].pb ( { i , b } ) ;
  102.         g[b].pb ( { i , a } ) ;
  103. 	}
  104.  
  105. 	for ( int i=0 ; i < n ; i ++ )
  106. 		ans[i] = inf ;
  107. }
  108.  
  109. map < pii , int > h ;
  110.  
  111. void take_queries()
  112. {
  113.     int q ; cin >> q ;
  114.  
  115.     while ( q -- )
  116. 	{
  117. 		int a , b , w ;
  118. 		cin >> a >> b >> w ;
  119.  
  120. 		a -- ; b -- ;
  121. 		if ( a > b ) swap ( a , b ) ;
  122.  
  123.         pii temp ;
  124.         temp.F = a ; temp.S = b ;
  125.  
  126.         if ( h.count ( temp ) )
  127. 		{
  128. 			if ( h[temp] != w )
  129. 				bad() ;
  130. 		}
  131.  
  132. 		h[temp] = w ;
  133. 	}
  134. }
  135.  
  136. vector < pair < pii , int > > v ;
  137.  
  138. bool comp ( const pair < pii , int > &a , const pair < pii , int > &b )
  139. {
  140. 	if ( a.S < b.S )
  141. 		return true ;
  142.  
  143. 	return false ;
  144. }
  145.  
  146. void sort_queries ()
  147. {
  148. 	int z = h.size() ;
  149. 	v.resize ( z ) ;
  150.  
  151. 	int indx = 0 ;
  152. 	for ( auto &temp : h )
  153. 		v[indx ++] = temp ;
  154.  
  155. 	sort ( allcomp ( v ) ) ;
  156. }
  157.  
  158. int src , des , w ;
  159. bool ok = false ;
  160.  
  161. void FILL()
  162. {
  163. 	for ( int i=0 ; i < n ; i ++ )
  164. 		vis[i] = false ;
  165. }
  166.  
  167. void dfs1 ( int node )
  168. {
  169.     vis[node] = 1 ;
  170.  
  171.     if ( node == des )
  172. 	{
  173. 		ok = true ;
  174. 		return ;
  175. 	}
  176.  
  177.     for ( auto &temp : g[node] )
  178. 	{
  179. 		int i = temp.S ;
  180. 		int indx = temp.F ;
  181.  
  182. 		if ( vis[i] ) C ;
  183.  
  184. 		dfs1 ( i ) ;
  185. 		if ( ok == false ) C ;
  186.  
  187.         ans[indx] = w ;
  188.         return ;
  189. 	}
  190. }
  191.  
  192. void read_queries()
  193. {
  194. 	for ( auto &temp : v )
  195. 	{
  196.         src = temp.F.F ;
  197.         des = temp.F.S ;
  198.         w = temp.S ;
  199.  
  200.         ok = false ; FILL() ;
  201.         dfs1 ( src ) ;
  202. 	}
  203. }
  204.  
  205. void dfs ( int node , int min_path = inf )
  206. {
  207. 	vis[node] = 1 ;
  208.  
  209. 	if ( node == des )
  210. 	{
  211. 		if ( min_path == w )
  212. 			ok = true ;
  213.  
  214. 		else bad() ;
  215. 	}
  216.  
  217. 	for ( auto &temp : g[node] )
  218. 	{
  219. 		int i = temp.S ;
  220. 		int indx = temp.F ;
  221.  
  222. 		if ( vis[i] ) C ;
  223.  
  224. 		dfs ( i , min ( min_path , ans[indx] ) ) ;
  225.  
  226. 		if ( ok ) return ;
  227. 	}
  228. }
  229.  
  230. void check_if_tree_ok()
  231. {
  232. 	for ( auto &temp : v )
  233. 	{
  234. 		src = temp.F.F ;
  235. 		des = temp.F.S ;
  236. 		w = temp.S ;
  237.  
  238. 		FILL() ; ok = false ;
  239. 		dfs ( src ) ;
  240.  
  241. 		if ( ok == false )
  242. 			bad() ;
  243. 	}
  244. }
  245.  
  246. void print_ans ()
  247. {
  248. 	int maxx = 1e6 ;
  249. 	for ( int i=0 ; i < n - 1 ; i ++ )
  250. 	{
  251. 		cout << min ( ans[i] , maxx ) << " " ;
  252. 	}
  253.  
  254. 	line ;
  255. }
  256.  
  257. void solve ( int test_case )
  258. {
  259.     read() ;
  260.     take_queries() ;
  261.     sort_queries() ;
  262.  
  263.     read_queries() ;
  264.     check_if_tree_ok() ;
  265.  
  266.     print_ans() ;
  267. }
  268.  
  269. int main()
  270. {fast
  271.     int t = 1;
  272.     // cin >> t;
  273.  
  274.     for ( int i=0 ; i < t ; i++ ) solve(i);
  275.     return 0;
  276. }
  277.  
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/DtpiMq
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (clang 8.0)

					

					

						
created:
								
						
4 years ago

					

					

						
visibility:

						

														 secret																					
							
							

								
							

						

					

										
										

					
					 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!