MLE on #2 求调
查看原帖
MLE on #2 求调
730959
hubin1楼主2024/8/8 10:48
#include<bits/stdc++.h>
using namespace std;

// #define int long long
#define debug(x,i) cerr<<#x<<"="<<x<<" \n"[i]

const int MAX=1e5+10;
const int mod=1e9+7;

vector<int>G[MAX];
vector<int>pri;
vector<int>val;
int sz[MAX];
int n;
bool cmp(int x,int y)
{
    if(x>y)
        return 1;
    else
        return 0;
}

void dfs(int u,int fa)
{
    sz[u]=1;
    for(int i:G[u])
    {
        if(i!=fa)
        {
            dfs(i,u);
            sz[u]=sz[u]+sz[i];
        }
    }
    if(u!=1)
    {
        // debug(sz[u]*(n-sz[u]),1);

        val.push_back(sz[u]*(n-sz[u]));
    }
}

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        
        for(int i=1;i<=n-1;i++)
        {
            G[i].clear();
            sz[i]=0;
        }
        pri.clear();
        val.clear();

        for(int i=1;i<=n-1;i++)
        {
            int u,v;
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int m;
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            int tmp;
            cin>>tmp;
            pri.push_back(tmp);
        }
        dfs(1,0);

        sort(val.begin(),val.end(),cmp);
        sort(pri.begin(),pri.end(),cmp);
        
        if(m<=n-1)//不够分的
        {
            // cout<<"sz"<<endl;
            // for(int i=1;i<=n;i++)
            //     cout<<sz[i]<<" ";
            // cout<<endl;

            // cout<<"val"<<endl;
            // cout<<"val.size="<<val.size()<<endl;
            // for(int i=0;i<val.size();i++)
            // {
            //     cout<<val[i]<<" ";
            // }
            // cout<<endl;
            for(int i=0;i<pri.size();i++)
            {
                val[i]=(val[i]*pri[i])%mod;
            }
        }
        else
        {
            int tmp=1;
            while(pri.size()>n-1)
            {
                tmp=(tmp*pri[0])%mod;
                pri.erase(pri.begin());
            }
            val[0]=(val[0]*tmp)%mod;
            for(int i=0;i<pri.size();i++)
            {
                val[i]=(val[i]*pri[i])%mod;
            }
        }

        int ans=0;
        for(int i=0;i<val.size();i++)
        {
            ans=(ans+val[i])%mod;
        }
        cout<<ans<<endl;
    }
    
    return 0;
}
2024/8/8 10:48
加载中...