只有第一个数据点AC,求条
查看原帖
只有第一个数据点AC,求条
1373959
bloxd楼主2025/7/1 18:21
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
vector<vector<pair<int, int> > > adjj;
vector<int> subt;
vector<int> fun;
vector<int> weii;
long long pairr;
void dfs(int curr, int fu) {
    subt[curr] = 1;
    for (auto &edge : adjj[curr]) {
        int nei = edge.first;
        int weight = edge.second;
        if (nei != fu) {
            fun[nei] = curr;
            weii[nei] = weight;
            dfs(nei, curr);
            subt[curr] += subt[nei];
        }
    }
}
int maintenance_costs_sum(vector<int> U, vector<int> V, vector<int> W) {
    int num = U.size() + 1;
    adjj.resize(num);
    subt.resize(num);
    fun.resize(num, -1);
    weii.resize(num);
    for (int i = 0; i < num - 1; ++i) {
        int u = U[i];
        int v = V[i];
        int w = W[i];
        adjj[u].emplace_back(v, w);
        adjj[v].emplace_back(u, w);
    }
    dfs(0, -1);
    pairr = (long long)num * (num + 1) / 2 % MOD;
    long long res = 0;
    for (int node = 1; node < num; ++node) {
        int size = subt[node];
        long long cnt = (pairr - (long long)size * (size + 1) / 2 % MOD - (long long)(num - size) * (num - size + 1) / 2 % MOD) % MOD;
        if (cnt < 0) cnt += MOD;
        res = (res + cnt * weii[node]) % MOD;
    }
    return (int)res;
}
2025/7/1 18:21
加载中...