QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62247 | #4544. Weighted Beautiful Tree | qinjianbin | AC ✓ | 1448ms | 87932kb | C++17 | 2.0kb | 2022-11-17 18:02:30 | 2022-11-17 18:02:30 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int c[N], a[N], n;
vector<ll> val[N], dp[N], pre[N], suf[N];
unordered_map<int, int> mp[N];
vector<pair<int, int>> g[N];
void dfs(int u, int fa)
{
dp[u].resize(val[u].size() + 1);
for(auto [v, w]: g[u])
{
if(v == fa) continue;
dfs(v, u);
int pv = mp[v][w];
ll cur = pre[v][pv];
int pu = mp[u][w];
dp[u][pu + 1] += cur;
cur = suf[v][pv];
dp[u][0] += cur;
dp[u][pu] -= cur;
dp[u][pu] += pre[v][val[v].size() - 1];
dp[u][pu + 1] -= pre[v][val[v].size() - 1];
}
// puts("!!");
// for(auto x: dp[u]) printf("%lld ", x); puts("");
rep(i, 1, val[u].size()) dp[u][i] += dp[u][i - 1];
rep(i, 0, val[u].size()) dp[u][i] += 1LL * c[u] * abs(val[u][i] - a[u]);
pre[u].resize(val[u].size());
suf[u].resize(val[u].size());
pre[u][0] = dp[u][0];
rep(i, 1, val[u].size()) pre[u][i] = min(dp[u][i], pre[u][i - 1]);
suf[u][val[u].size() - 1] = dp[u][val[u].size() - 1];
for(int i = val[u].size() - 2; i >= 0; i--)
suf[u][i] = min(dp[u][i], suf[u][i + 1]);
// puts("##!");
// for(auto x: dp[u]) printf("%lld ", x); puts("");
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
_for(i, 1, n) scanf("%d", &c[i]), g[i].clear(), val[i].clear(), mp[i].clear(), dp[i].clear(), pre[i].clear(), suf[i].clear();
_for(i, 1, n) scanf("%d", &a[i]), val[i].push_back(a[i]);
_for(i, 1, n - 1)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
val[u].push_back(w);
val[v].push_back(w);
}
_for(i, 1, n)
{
sort(val[i].begin(), val[i].end());
rep(j, 0, val[i].size()) mp[i][val[i][j]] = j;
}
dfs(1, 0);
ll ans = 1e18;
rep(i, 0, dp[1].size() - 1)
ans = min(ans, dp[1][i]);
printf("%lld\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1448ms
memory: 87932kb
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