QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#129770#4544. Weighted Beautiful Treebatrr#AC ✓354ms41912kbC++173.2kb2023-07-22 23:33:372023-07-22 23:33:38

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-22 23:33:38]
  • 评测
  • 测评结果:AC
  • 用时:354ms
  • 内存:41912kb
  • [2023-07-22 23:33:37]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}

vector<pii> g[N];
int n;
ll v_cost[N], v_weight[N], e_weight[N];

ll conds_n, conds[N], val[N];

ll dp[N][2], ans;

// 0 v <= w[pe]
// 1 v >= w[pe]

void add(int l, int r, ll x){
    if(l > r)
        return;
    val[l] += x;
    val[r + 1] -= x;
}
void dfs(int v, int pe) {
    dp[v][0] = dp[v][1] = INF;
    for (auto it: g[v]) {
        int to = it.f;
        int e = it.s;
        if (e == pe)
            continue;
        dfs(to, e);
    }

    sort(g[v].begin(), g[v].end(), [](pii i, pii j) {
        return e_weight[i.s] < e_weight[j.s];
    });
    conds_n = 0;
    conds[conds_n++] = v_weight[v];
    for (auto it: g[v]) {
        int to = it.f;
        int e = it.s;
        if (e == pe)
            continue;
        conds[conds_n++] = e_weight[e];
    }
    if (pe != -1)
        conds[conds_n++] = e_weight[pe];
    sort(conds, conds + conds_n);
    conds_n = unique(conds, conds + conds_n) - conds;
    for(int i = 0; i < conds_n; i++)
        val[i] = 0;
    for (auto it: g[v]) {
        int to = it.f;
        int e = it.s;
        if (e == pe)
            continue;
        int pos = lower_bound(conds, conds + conds_n, e_weight[e]) - conds;
        add(0, pos - 1, dp[to][1]);
        add(pos, pos, min(dp[to][0], dp[to][1]));
        add(pos + 1, conds_n - 1, dp[to][0]);
    }
    ll x = 0;
    for(int i = 0; i < conds_n; i++){
        x += val[i];
        ll cur = x + abs(conds[i] - v_weight[v]) * v_cost[v];
        if(pe == -1){
            ans = min(ans, cur);
        }else{
            if(conds[i] <= e_weight[pe])
                dp[v][0] = min(dp[v][0], cur);
            if(conds[i] >= e_weight[pe])
                dp[v][1] = min(dp[v][1], cur);
        }
    }
//    cerr << v << " " << dp[v][0] << " " << dp[v][1] << endl;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v_cost[i];
    for (int i = 0; i < n; i++)
        cin >> v_weight[i];
    for (int i = 0; i < n - 1; i++) {
        int v, u;
        cin >> v >> u >> e_weight[i];
        v--, u--;
        g[v].pb({u, i});
        g[u].pb({v, i});
    }
    ans = INF;
    dfs(0, -1);
    cout << ans << "\n";
    for(int i = 0; i < n; i++)
        g[i].clear();
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 354ms
memory: 41912kb

input:

1000
3
2 1 2
9 9 10
1 2 10
1 3 11
3
1 1 2
9 9 10
1 2 10
1 3 11
99991
914575 436426 979445 648772 690081 933447 190629 703497 47202 407775 894325 963982 804784 968417 302156 631932 735902 895728 78537 723857 330739 286918 329211 539679 238506 63340 686568 361868 660016 287940 296263 224593 601449 836...

output:

3
2
7472540655778111
7473294329562293
8345692029003633
7238550879556940
7841133629861454
4971153421
8181537378
1893424
8143454283
9109290590
11153093754
528748866106540
2081626582
856886106916260
9930470
22231658010804
15244442281704
523150824
0
14045371538269
37592337
45122406677153
184107700398848...

result:

ok 1000 lines