Submission #550186

#	Time	Username	Problem	Language	Result	Execution time	Memory
550186		Duy_e	Beads and wires (APIO14_beads)	C++14	28 / 100	1093 ms	5428 KiB

beads

/*
**  TASK: 
**  LINK: 
*/

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;

struct edge {
    ll u, v, w;
} g[N];

vector <int> d[N];

int n;
ll dp[N][2]; 

/*
    0: là node được nối với dây đỏ
    1: là node được thêm sau 2 node trước
*/

void dfs(int p, int u) {

    ll s0 = 0;
    vector <int> f; f.push_back(0);
    for (int i: d[u]) {
        int v = g[i].u ^ g[i].v ^ u;
        int w = g[i].w;
        if (v == p) continue;
        dfs(u, v);
        s0 += dp[v][0];
        if (d[v].size() == 1) dp[v][1] = -INF;

        f.push_back(f.back() + max(dp[v][0], dp[v][1] + w));
    }

    f.push_back(f.back());

    dp[u][0] = s0;
    int pos = 1;
    for (int i: d[u]) {
        int v = g[i].u ^ g[i].v ^ u;
        int w = g[i].w;

        if (v == p) continue;
        
        dp[u][1] = max(dp[u][1], f[pos - 1] + f[f.size() - 1] - f[pos] + dp[v][0] + w);
        dp[u][0] = max(dp[u][0] + dp[v][1] + w - dp[v][0], dp[u][0]);
        pos ++;
    }

    // cout << u << ": " << dp[u][0] << ' ' << dp[u][1] << ' ' << d[u].size() << '\n';
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    // #endif
    
    cin >> n;
    for (int i = 1; i < n; i ++) {
        cin >> g[i].u >> g[i].v >> g[i].w;
        d[g[i].u].push_back(i);
        d[g[i].v].push_back(i);
    }

    ll ans = 0;

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= n; j ++)
            dp[j][0] = dp[j][1] = 0;
        dfs(0, i);

        ans = max(ans, dp[i][0]);
        // cout << i << ' ' << dp[i][0] << '\n';
    }

    cout << ans;

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮

1 node chỉ có thể được nối với tối đa là 2 dây xanh và chỉ có thể có đúng 2 dây xanh liên tiếp?



2 thao tác:
+ append(w, v): gắn nút w mới vào một nút v "ĐÃ TỒN TẠI"
-> nếu fix root của 1 subtree root v thì v không thể được thêm vào sau 2 nút con được

+ insert(w, u, v): gắn nút w mới vào giữa 2 nút u, v "ĐÃ TỒN TẠI"

3 sub đầu dp n ^ 2 -> solve for each root

**/

Compilation message (stderr)

beads.cpp:93:9: warning: "/*" within comment [-Wcomment]
   93 | /**  /\_/\
      |

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43