1 条题解

  • 0
    @ 2025-6-8 9:55:58
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN = 500000 + 5;
    int n, s;
    struct Edge
    {
        int v, w;
    };
    vector<Edge> e[MAXN];
    int dp[MAXN], len[MAXN];
    void dfs(int u, int fa)
    {
        int maxLen = 0;
        dp[u] = 0;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (v == fa)
                continue;
            dfs(v, u);
            maxLen = max(maxLen, w + len[v]);
            dp[u] += dp[v];
        }
        len[u] = maxLen;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (v == fa)
                continue;
            dp[u] += maxLen - (w + len[v]);
        }
    }
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> s;
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            e[u].push_back((Edge){v, w});
            e[v].push_back((Edge){u, w});
        }
        dfs(s, 0);
        cout << dp[s];
        return 0;
    }
    
    • 1

    信息

    ID
    1954
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    18
    已通过
    8
    上传者