이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1<<17;
int n, q; ll ans[N];
vector<array<int, 3>> adj[N];
namespace Task1{
ll sum, cur;
void dfs1(int v, int p){
for(auto [u, d1, d2] : adj[v]){
sum += d2;
if(u==p) continue;
cur += d2;
dfs1(u, v);
}
}
void dfs2(int v, int p){
ans[1] = min(ans[1], sum-cur);
for(auto [u, d1, d2] : adj[v]){
if(u==p) continue;
cur -= d2; cur += d1;
dfs2(u, v);
cur += d2; cur -= d1;
}
}
void solve(){
dfs1(0, 0);
dfs2(0, 0);
}
}
namespace Task2{
ll sum, tot, dp[N], best[N];
int best1, best2;
void dfs1(int v, int p){
for(auto [u, d1, d2] : adj[v]){
sum += d2;
if(u==p) continue;
tot += d2;
dfs1(u, v);
}
}
void dfs2(int v, int p, ll val1, ll val2){
ll tmp = tot-val1+val2;
array<ll, 2> mx1 = {0, v}, mx2 = {0, v};
best[v] = v;
for(auto [u, d1, d2] : adj[v]){
if(u==p) continue;
dfs2(u, v, val1+d2, val2+d1);
if(dp[u]+d1>dp[v])
dp[v] = dp[u]+d1, best[v] = best[u];
if(array<ll, 2>{dp[u]+d1, best[u]}>mx1)
mx2 = mx1, mx1 = {dp[u]+d1, best[u]};
else if(array<ll, 2>{dp[u]+d1, best[u]}>mx2)
mx2 = {dp[u]+d1, best[u]};
}
if(sum-tmp-mx1[0]-mx2[0]<ans[2])
best1 = mx1[1], best2 = mx2[1], ans[2] = sum-tmp-mx1[0]-mx2[0];
}
void solve(){
dfs1(0, 0);
dfs2(0, 0, 0, 0);
}
}
namespace Task3{
int rt;
array<ll, 2> tree[N<<1]; ll lazy[N<<1];
int fa[N], idx[N];
int tin[N], tout[N], tid;
ll sum, cur, up[N];
bool vis[N];
void push(int v, int tl, int tr){
tree[v][0] += lazy[v];
if(tl!=tr)
lazy[v<<1] += lazy[v],
lazy[v<<1|1] += lazy[v];
lazy[v] = 0;
}
void upd(int l, int r, ll val, int v = 1, int tl = 0, int tr = N-1){
push(v, tl, tr);
if(tr<l || tl>r) return;
if(l<=tl && tr<=r){
lazy[v] += val;
push(v, tl, tr);
return;
}
int tm = (tl+tr)>>1;
upd(l, r, val, v<<1, tl, tm);
upd(l, r, val, v<<1|1, tm+1, tr);
tree[v] = max(tree[v<<1], tree[v<<1|1]);
}
void dfs1(int v, int p, ll dep){
fa[v] = p;
tin[v] = ++tid;
idx[tid] = v;
upd(tin[v], tin[v], dep);
for(auto [u, d1, d2] : adj[v]){
sum += d2;
if(u==p) continue;
cur += d2;
up[u] = d1;
dfs1(u, v, dep+d1);
}
tout[v] = tid;
}
void solve(){
for(int i = N; i<2*N; ++i)
tree[i][1] = i-N;
dfs1(rt, rt, 0);
vis[rt] = 1;
for(int i = 2; i<=n; ++i){
ans[i] = i==2?sum-cur:ans[i-1];
int v = idx[tree[1][1]];
ans[i] -= tree[1][0];
while(!vis[v]){
vis[v] = 1;
upd(tin[v], tout[v], -up[v]);
v = fa[v];
}
}
}
}
int main(){
// freopen("a.in", "r", stdin);
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 0; i<n-1; ++i){
int a, b, c, d;
cin >> a >> b >> c >> d;
--a; --b;
adj[a].push_back({b, c, d});
adj[b].push_back({a, d, c});
}
memset(ans, 63, sizeof ans);
Task1::solve();
Task2::solve();
Task3::rt = Task2::best1;
Task3::solve();
cin >> q;
while(q--){
int x; cin >> x;
cout << ans[x] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |