This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
struct edge{
int a, b, c, d;
ll get(int v){
if(v == b) return c;
else return d;
}
int ano(int v){
return a ^ b ^ v;
}
};
vector<vector<edge>> g;
vector<ll> dp, ans, ans2, dp2;
void dfs(int now, int p){
//cerr << "dfs " << now << "\n";
vector<ll> t;
for(edge i : g[now]){
int v = i.ano(now);
if(v == p) continue;
dfs(v, now);
dp[now] += i.get(v) + dp[v];
dp2[now] = max(dp2[now], i.get(v) + dp2[v]);
t.eb(i.get(v) + dp2[v]);
}
sort(t.begin(), t.end(), greater<>());
if(t.size() >= 2) ans2[now] = t[0] + t[1];
else ans2[now] = dp2[now];
}
void dfs2(int now, int p){
for(edge i : g[now]){
int v = i.ano(now);
if(v == p){
//cerr << "dfs2 " << now << " " << p << " " << ans[p] << " " << i.get(now) << " " << i.get(p) << "\n";
ans[now] = ans[p] - i.get(now) + i.get(p);
continue;
}
}
for(edge i : g[now]){
int v = i.ano(now);
if(v != p) dfs2(v, now);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
g.resize(n + 1);
dp.resize(n + 1);
ans.resize(n + 1);
ans2.resize(n + 1);
dp2.resize(n + 1);
for(int i = 0; i < n - 1; i++){
int u, v, c, d;
cin >> u >> v >> c >> d;
g[u].eb(edge({u, v, c, d}));
g[v].eb(edge({u, v, c, d}));
}
dfs(1, 1);
ans[1] = dp[1];
dfs2(1, 1);
ll mn = 1LL << 60;
for(int i = 1; i <= n; i++) mn = min(mn, ans[i] - ans2[i]);
//printv(dp, cerr);
//printv(ans, cerr);
int q;
cin >> q;
while(q--){
int e;
cin >> e;
cout << mn << "\n";
}
return 0;
}
# | 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... |