Untitled Diff
9 removals
72 lines
16 additions
79 lines
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
using namespace std;
#define int long long
#define int long long
#define ll long long
#define ll long long
const ll M = 1000000007;
const ll M = 1000000007;
#define pb push_back
#define pb push_back
#define forn(i,k,n) for(int i = k; i < n; ++i)
#define forn(i,k,n) for(int i = k; i < n; ++i)
#define nfor(i,n,k) for(int i = n; i >= k; --i)
#define nfor(i,n,k) for(int i = n; i >= k; --i)
#define all(arr) arr.begin(), arr.end()
#define all(arr) arr.begin(), arr.end()
#define endl '\n'
#define endl '\n'
#define N 100015
#define N 100015
ll n;
ll n;
vector<ll> G[N];
vector<ll> G[N];
multiset<ll,greater<ll>> s;
multiset<ll,greater<ll>> s;
vector<ll> C(N);
vector<ll> C(N);
// dfs function to calculate no of nodes in subtree of u..
// dfs function to calculate no of nodes in subtree of u..
// and then inserting the contribution of each edge in the set s
// and then inserting the contribution of each edge in the set s
ll dfs(ll u, ll p){
ll dfs(ll u, ll p){
C[u] = 0;
C[u] = 0;
ll tmp = 0;
ll tmp = 0;
for(auto x: G[u]){
for(auto x: G[u]){
if(x == p) continue;
if(x == p) continue;
C[x] += dfs(x,u) + 1;
C[x] += dfs(x,u) + 1;
C[x] %= M;
C[x] %= M;
tmp += C[x];
tmp += C[x];
tmp %= M;
tmp %= M;
s.insert(((C[x] % M) * (n - C[x]) % M) % M); // contribution is (subtree nodes * (total nodes - subtree nodes))...
// don't add mod values since they might become smaller!
s.insert(C[x] * (n - C[x])); // contribution is (subtree nodes * (total nodes - subtree nodes))...
}
}
return tmp % M;
return tmp % M;
}
}
void solve(){
void solve(){
// input and clearing of Data structures
// input and clearing of Data structures
s.clear();
s.clear();
cin >> n;
cin >> n;
forn(i,1,n + 1) G[i].clear();
forn(i,1,n + 1) G[i].clear();
C.clear();
C.clear();
forn(i,1,n){
forn(i,1,n){
ll u, v; cin >> u >> v;
ll u, v; cin >> u >> v;
G[u].pb(v);
G[u].pb(v);
G[v].pb(u);
G[v].pb(u);
}
}
dfs(1,0); // dfs to calculate contribution
dfs(1,0); // dfs to calculate contribution
ll m; cin >> m;
ll m; cin >> m;
multiset<ll,greater<ll>> fac; // multiset for factors of k
multiset<ll,greater<ll>> fac; // multiset for factors of k
forn(i,0,m){
forn(i,0,m){
ll xx; cin >> xx;
ll xx; cin >> xx;
fac.insert(xx);
fac.insert(xx);
}
}
while(fac.size() < n - 1) fac.insert(1); // inserting 1 for each left nodes if (m < n - 1)
while(fac.size() < n - 1) fac.insert(1); // inserting 1 for each left nodes if (m < n - 1)
ll ans = 0;
ll ans = 0, product=1;
while(fac.size() > n - 1){ // multiplying greatest factors of k till the size of m is n - 1; if(m > n - 1)
// don't add add mod values since they might become smaller!
while(fac.size() > n - 2){ // multiplying greatest factors of k till the size of m is n - 1; if(m > n - 1)
ll tmp = *fac.begin();
ll tmp = *fac.begin();
fac.erase(fac.begin());
fac.erase(fac.begin());
ll tmp2 = *fac.begin();
product = (product * tmp) % M;
fac.erase(fac.begin());
fac.insert(((tmp % M) * (tmp2 % M)) % M);
}
}
ans += (product * ((*s.begin()) % M)) % M;
s.erase(s.begin());
auto it = fac.begin();
auto it = fac.begin();
// calculating total answer by multiplying contribution of each edge by factors of k (we multiply highest contribution by highest factor))...
// calculating total answer by multiplying contribution of each edge by factors of k (we multiply highest contribution by highest factor))...
for(auto x : s){
for(auto x : s){
ans += ((x % M) * ((*it) % M)) % M;
ans += ((x % M) * ((*it) % M)) % M;
ans %= M;
ans %= M;
it++;
it++;
}
}
cout << ans % M << endl;
cout << ans % M << endl;
}
}
signed main(){
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin >> t;
int t; cin >> t;
while(t--) solve();
while(t--) solve();
return 0;
return 0;
}
}