제출 #1325057

#제출 시각아이디문제언어결과실행 시간메모리
1325057NValchanov구슬과 끈 (APIO14_beads)C++20
100 / 100
237 ms29720 KiB
#include <iostream>
#include <vector>

using namespace std;

typedef long long llong;

const int MAXN = 2e5 + 10;
const llong INF = 4e18 + 10;

struct Edge
{
    int to;
    int cost;

    Edge(){};

    Edge(int to, int cost)
    {
        this->to = to;
        this->cost = cost;
    }
};

int n;
vector < Edge > adj[MAXN];
llong dp[MAXN][2];
llong up[MAXN][2];
pair < llong, int > minch[MAXN][2];
llong ans;

void read()
{
    cin >> n;

    for(int i = 1; i < n; i++)
    {
        int u, v, cost;
        cin >> u >> v >> cost;

        adj[u].push_back(Edge(v, cost));
        adj[v].push_back(Edge(u, cost));
    }
}

void dfs(int u, int par)
{
    minch[u][0] = minch[u][1] = {INF, 0};

    for(Edge &e : adj[u])
    {
        int v = e.to;
        int cost = e.cost;

        if(v == par)
            continue;

        dfs(v, u);

        llong cur = max(dp[v][0], dp[v][1] + cost);

        dp[u][0] += cur;

        pair < llong, int > opt = {cur - dp[v][0] - cost, v};

        if(opt < minch[u][0])
        {
            minch[u][1] = minch[u][0];
            minch[u][0] = opt;
        }
        else if(opt < minch[u][1])
        {
            minch[u][1] = opt;
        }
    }

    if(adj[u].size() == 1)
        dp[u][1] = -INF;
    else
        dp[u][1] = dp[u][0] - minch[u][0].first;
}

void dfs2(int u, int par)
{
    for(Edge &e : adj[u])
    {
        int v = e.to;
        int cost = e.cost;

        if(v == par)
            continue;

        llong cur = max(dp[v][0], dp[v][1] + cost);

        llong f0 = dp[u][0] + up[u][0] - cur;
        llong f1 = dp[u][0] + up[u][1] - cur;

        if(u == 1)
            f1 = -INF;

        llong opt = dp[u][1] + up[u][0] - cur;

        if(minch[u][0].second == v)
        {
            opt += minch[u][0].first;
            opt -= minch[u][1].first;
        }

        f1 = max(f1, opt);

        up[v][0] = max(f0, f1 + cost);
        up[v][1] = f0 + cost;

        ans = max(ans, up[v][0] + dp[v][0]);

        dfs2(v, u);
    }
}

void solve()
{
    dfs(1, 1);

    ans = dp[1][0];

    dfs2(1, 1);

    cout << ans << endl;
}

int main()
{
    read();
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...