时间戳

首页 > 解决方案 > 求加权树中每对节点之间的边权重之和

c++ - 求加权树中每对节点之间的边权重之和

问题描述

我需要找到一种有效的方法来找到加权树中所有简单路径的值之和。简单路径的值定义为给定简单路径中所有边的权重之和。

这是我的尝试，但它不起作用。请告诉正确的做法。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, ll> pil;
const int MAXN = 1e5;
int n, color[MAXN + 2];
vector<pil> adj[MAXN + 2];
ll sum1, cnt1[MAXN + 2], cnt[MAXN + 2], res;

void visit(int u, int p)
{
    cnt[u] = 1;

    cnt1[u] = color[u];

    for (int i = 0; i < (int) adj[u].size(); ++i)
    {
        int v = adj[u][i].first;
        ll w = adj[u][i].second;

        if (v == p)
            continue;

        visit(v, u);
        ll tmp = cnt1[v] * (n - sum1 - cnt[v] + cnt1[v]);
        tmp += (cnt[v] - cnt1[v]) * (sum1 - cnt1[v]);
        res += tmp * w;

        cnt[u] += cnt[v];
        cnt1[u] += cnt1[v];
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", color + i);
        sum1 += color[i];
    }

    for (int i = 1, u, v; i < n; ++i)
    {
        scanf("%d %d %lld", &u, &v, &res);
        adj[u].push_back(pil(v, res));
        adj[v].push_back(pil(u, res));
    }

    res = 0;

    visit(1, -1);
    printf("%lld\n", res);
    return 0;
}

标签： c++data-structuresgraphc++14c++17

解决方案

以下是@Arjun Singh 解释的简单实现。

int64_t ans = 0;

int dfs(int node, int parent) {
    int cur_subtree_size = 1;
    for(int child : adj[node]) {
        if(parent != child) {
            int child_subtree_size = dfs(child, node);
            int64_t contribution_of_cur_edge = child_subtree_size * (N - child_subtree_size) * weight[{node, child}];
            ans += contribution_of_cur_edge;
            cur_subtree_size += child_subtree_size;
        }
    }
    return cur_subtree_size;
}

推荐阅读