Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
90598516 Contestant:
roshan_mehta
1401D - 33 C++17 (GCC 9-64) Wrong answer on pretest 5 77 ms 15924 KB 2020-08-21 18:54:33 2020-08-21 18:54:33
→ Source
        // "It does not matter how slowly you go as long as you do not stop." - Confucius
#include <bits/stdc++.h>

using namespace std;

/*
author : Roshan_Mehta
motto : Time Management,Consistency,Patience!!
*/

#define int long long

#ifdef Local_Debug

#define debug(x) cout<<#x <<" "<<x<<"  "
#define debug1(a) cout <<#a<<" " <<a << endl
#define debug2(a, b) cout <<#a<<" "<< a << " "<<#b<<" " << b << endl
#define debug3(a, b, c) cout <<#a<<" "<<a << " "<<#b<<" " << b << " "<<#c<<" " << c << endl
#define debug4(a, b, c, d) cout << #a<<" "<<a << " " <<#b<<" "<< b << " "<<#c<<" " << c << " "<<#d<<" "<< d << endl
void show(vector<int> &a)
{for (int i = 0; i < a.size(); i++)
{cout << a[i] << " ";}cout << endl;}
void show(vector<vector<int>> &a)
{
    for(int i=0;i<a.size();i++)
    {
        for(int j=0;j<a[i].size();j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
void show(vector<pair<int,int>> &a)
{
    for (int i = 0; i < (int)a.size(); i++)
    {
        cout<<a[i].first<<" "<<a[i].second<<endl;
    }

}
void printTime(clock_t begin)
{
    printf("%.3lf seconds\n", (double) (clock() - begin) / CLOCKS_PER_SEC);

}
#else
#define debug(x)
#define debug1(x)
#define debug2(x,y)
#define debug3(x,y,z)
#define debug4(x,y,z,a)
void show(vector<int> &a){return;}
void show(vector<vector<int>> &a){return;}
void show(vector<pair<int,int>> &a){return ;}
void printTime()
{return;}
#endif


#define M1 1000000007
#define M2 998244353
#define G(a,b) get<a>(b)
#define ll long long
#define pb push_back
#define mt make_tuple
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rsort(x) sort(x,greater<int> ())
#define rall(x) rbegin(x), rend(x) //useful in sorting
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
#define gcd __gcd
#define deci(n) fixed << setprecision(n)
#define test() int test_case;cin >> test_case;while (test_case--)
#define loop(i,a,n) for(int i=a;i<n;i++)
#define sp " "
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define clz(x) __builtin_clz(x)
#define clzll(x) __builtin_clzll(x)
#define ctz(x) __builtin_ctz(x)
#define ctzll(x) __builtin_ctzll(x)
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define max4(a,b,c,d) max(a,max3(b,c,d))
#define min4(a,b,c,d) min(a,min3(b,c,d))
#define max5(a,b,c,d,e) max(max4(a,b,c,d),e)
#define min5(a,b,c,d,e) min(min4(a,b,c,d),e)
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define REPI(i,a,b) for(ll i=b-1;i>=a;i--)

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef pair<int,pi> tri;
typedef pair<pi,int> rtri;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef priority_queue<int, vector<int>, greater<int>> minpq;
typedef priority_queue<int> pq;
typedef unordered_map<int,int> umii;
typedef map<int,int> mii;
typedef set<int> si;
#define input(n,k) int n,k;cin>>n;cin>>k;vi arr(n,0);loop(i,0,n){cin>>arr[i];}

const int MOD = 1e9 + 7;
int md=MOD;

int Power(int n, int x) {int ans = 1;while (x > 0) {if (x & 1) ans = (ans * n) % md;
n = (n * n) % md;x = x >> 1;}return ans;}

vl fact, inv;

void inverse(ll n)
{if(n>=inv.size()){ll size=inv.size();size=size==0? 1:size;
inv.resize(n + 1);inv[0] = 1;
for (ll i = size; i <= n; i++)inv[i] = Power(fact[i], md - 2);}}

void factorial(ll n)
{if(n>=fact.size()){ll size=fact.size();size=size==0? 1:size;
fact.resize(n + 1);fact[0] = 1;for (ll i = size; i <= n; i++)
fact[i] = (fact[i - 1] * i) % md;
}}

ll ncr(ll n, ll r) { return (((fact[n] * inv[r]) % md) * inv[n - r]) % md; }

vl SieveOfEratosthenes(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));
    for (int p=2; p*p<=n; p++)
    {if (prime[p] == true){for (int i=p*p; i<=n; i += p)
    prime[i] = false;}}

    vl ans;for (int p=2; p<=n; p++)if (prime[p])ans.pb(p);return ans;
}
vi primeFactors(int n)
{
    vi ans;
    while (n % 2 == 0) {ans.pb(2);n = n / 2;}
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {ans.pb(i);n = n / i;}}
    if (n > 2)ans.pb(n);return ans;
}

ll NcR(int n, int r)
{long long p = 1, k = 1;if (n - r < r)r = n - r;if (r != 0) {while (r) {p *= n;k *= r;
long long m = gcd(p, k);p /= m;k /= m;n--;r--;}
}else p = 1;return p;// cout << p << endl;
}
bool sortasc(const rtri a,const rtri b) //Ascending ... change the argument accordingwise;
{
    return a.second<b.second;
}
bool sortdesc(const int a,const int b) //Descending... change the argument accordingwise;a
{
    return a>b;
}
int myceil(int num,int den)
{
    return num%den == 0 ? num/den : num/den + 1;
}
int myfloor(int num,int den)
{
    return num%den == 0 ? num/den : num/den - 1;
}
string to_str(char c) {
	return string(1, c);
}
// 2-D vector with both size--> vector<vector<int> > a(n, vector<int>(m));

#define pie 3.141592653589793238462643383279
const int N = 2e5 + 5;

void ipgraph(int n, int m);void dfs(int u, int par);void bfs(int start);void iptree(int n);
vi topological_sort(const vvi &a);
//********************THE END OF TEMPLATES*******************//
void q1();
vvi adj;
vb visited(N);
vpi edgelist;
vi nodes;
vi parent;

int32_t main()
{
    clock_t begin = clock();
    fast();
    #ifdef Local_Debug
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
    #endif
    test()
    {
        q1();
    }

    return 0;
}
void q1()
{
    int n;
    cin>>n;
    adj=vvi(n);
    edgelist=vpi(n-1);
    parent=vi(n);
    ipgraph(n,n-1);
    nodes=vi(n);
    int m;
    cin>>m;
    vi val;
    for (int i = 0; i < m; i++)
    {
        int a;
        cin>>a;
        val.pb(a);
    }
    while(sz(val)<n-1)
        val.pb(1);
    show(val);
    sort(all(val),greater<int>());
    parent[0]=-1;
    dfs(0,-1);
    vi freq;
    show(edgelist);
    show(nodes);
    for (auto &&x : edgelist)
    {
        if(parent[x.F]!=x.S)
        {
            freq.pb(nodes[x.S]*(n-nodes[x.S])%M1);
        }
        else
        {
            freq.pb(nodes[x.F]*(n-nodes[x.F])%M1);
        }

    }
    sort(all(freq),greater<int>());
    show(freq);
    int j=sz(val)-1;
    int ans=0;
    for (int i = sz(freq) - 1; i >= 1; i--)
    {
        ans=(ans+((freq[i]%M1)*(val[j--]%M1))%M1)%M1;
    }
    int temp=1;
    for (int i = j; i >= 0; i--)
    {
        temp=(temp*(val[i]%M1))%M1;
    }
    ans=(ans+(temp*freq[0])%M1)%M1;
    cout<<ans<<endl;





}

void iptree(int n){  //n is number of node
    for (int i = 0; i < n-1; i++){             //0-based index
        int a;cin>>a;
        adj[i+1].pb(a-1);
        adj[a-1].pb(i+1);
    }

}

void ipgraph(int n, int m){               //0-based index
	int i, u, v;
    int t=0;
	while(m--){
		cin>>u>>v;
    u--, v--;
    edgelist[t++]={u,v};
		adj[u].pb(v);
		adj[v].pb(u);
	}
}

void dfs(int u, int par){
    // visited[u]=1;
    parent[u]=par;
    nodes[u]=1;
	for(int v:adj[u]){
		if (v == par) continue;
		dfs(v, u);
        nodes[u]+=nodes[v];
	}
}

void bfs(int start){
    queue<int> Q;
    Q.push(start);
    visited[start]=1;
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        for (auto &&i : adj[v]){
            if(!visited[i])
            {
                visited[i]=1;
                Q.push(i);
            }
        }

    }
}

// Note: if there is a cycle, the size of the return will be less than n.(from neal template round 660)
vector<int> topological_sort(const vector<vector<int>> &adj) {
    int n = (int)(adj.size());
    vector<int> in_degree(n, 0);
    vector<int> order;

    for (int i = 0; i < n; i++)
        for (int neighbor : adj[i])
            in_degree[neighbor]++;

    for (int i = 0; i < n; i++)
        if (in_degree[i] == 0)
            order.push_back(i);

    int current = 0;

    while (current < (int)order.size()) {
        int node = order[current++];

        for (int neighbor : adj[node])
            if (--in_degree[neighbor] == 0)
                order.push_back(neighbor);
    }

    return order;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details