fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define tc int t;cin>>t;while(t--)
  4. #define pb push_back
  5. #define mp make_pair
  6. #define pf push_front
  7. #define ll long long
  8. #define bp pop_back
  9. #define vt vector
  10. #define F first
  11. #define S second
  12. #define SORT(v) sort(v.begin(),v.end())
  13. ll M=1e9+7;
  14. ll n;
  15. ll dfs(vt<ll> v[],ll i,ll j,vt<ll> &w){
  16. 	if(v[i].size()==1 && i !=1) return 0;
  17. 	ll ans=0;
  18. 	for(ll k=0;k<v[i].size();k++){
  19. 		if(v[i][k] !=j){
  20. 			ans = dfs(v,v[i][k],i,w);
  21. 		}
  22. 		ans +=1;
  23. 		cout<<ans*(n-ans)<<" ";
  24. 		w.pb(ans*(n-ans));
  25. 	}
  26. 	return ans;
  27. }
  28. int main() {
  29. 	tc{
  30. 		ll m,ans=0; cin>>n;
  31. 		vt<ll> v[n+1];
  32. 		ll x,y;
  33. 		for(ll i=1;i<n;i++){
  34. 			cin>>x>>y;
  35. 			v[x].pb(y);
  36. 			v[y].pb(x);
  37. 		}
  38. 		cin>>m;
  39. 		ll a[m];
  40. 		for(int i=0;i<m;i++)  cin>>a[i];
  41. 		sort(a,a+m);
  42. 		vt<ll> w;
  43.         x=dfs(v,1,n+1,w);
  44. 		SORT(w);
  45. 		if(m<=n-1){
  46. 			x=n-2;
  47. 			 y=m-1;
  48. 			while(y>=0){
  49. 				ans +=((a[y]*w[x]))%M;
  50. 				ans %=M;
  51.  
  52. 				y--;
  53. 				x--;
  54. 			}
  55. 			while(x>=0){
  56. 				ans +=w[x];
  57. 				ans %=M;
  58. 				x--;
  59. 			}
  60. 			cout<<ans<<endl;
  61. 		}
  62. 		else{
  63. 			ans =1;
  64. 			 x=m-1;
  65. 			 y=n-2;
  66. 			while(x>=n-2){
  67. 				ans *=a[x];
  68. 				ans %=M;
  69. 				x--;
  70. 			}
  71. 			ans *=w[y];
  72. 			ans %=M;
  73. 			y--;
  74. 			while(y>=0){
  75. 				ans +=(a[y]*w[y])%M;
  76. 				ans %=M;
  77. 				y--;
  78. 			}
  79. 			cout<<ans<<endl;
  80. 		}
  81. 	}
  82. 	// your code goes here
  83. 	return 0;
  84. }
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
3
4
1 2
2 3
3 4
2
2 2
4
3 4
1 3
3 2
2
3 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3
stdout
copy 
3 3 3 4 3 15
3 4 3 4 21
6 6 6 6 10 12 12 6 232
https://ideone.com/vgJBvR
language:
C++14 (gcc 8.3)
created:
3 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!