5分求调
查看原帖
5分求调
354666
清溪墨染楼主2024/12/5 21:43

大佬们,我想的是先求子树中节点的个数,然后用题解中给出的公式去计算,但是为什么只对了第一个点

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
long long n;
vector<vector<pair<long long, long long>>> tree;
vector<bool> visited;
vector<long long> subtreeNumber;
void dfs(long long node){
    visited[node] = true;
    for(auto edge : tree[node]){
        if(!visited[edge.first]){
            dfs(edge.first);
            subtreeNumber[node] += subtreeNumber[edge.first];
        }
    }
}
int main(){
    cin >> n;
    tree.resize(n + 1);
    visited.resize(n + 1, false);
    subtreeNumber.resize(n + 1, 1);//每个子树一开始肯定包括自己
    long long a, b, c;
    for(long long i = 0; i < n - 1; i++){
        cin >> a >> b >> c;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }
    dfs(1);
    long long answer = 0;
    for(long long i = 1; i <= n; i++){
        for(auto neighbor : tree[i]){
            //遍历每个节点的时候,都只计算相邻节点中较大的那一个
            if(neighbor.first > i){
                answer += neighbor.second * abs(2 * subtreeNumber[neighbor.first] - n);
            }
        }
    }
    cout << answer;
}
2024/12/5 21:43
加载中...