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
using namespace std;
typedef long long ll;
const int MAXN = 200055;
vector<int> G[MAXN];
int prt[MAXN], dep[MAXN], cnt[MAXN], dfo[MAXN];
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
ll Ans[MAXN], Sum;
int N, Q;
void predfs(int i, int &c) {
cnt[i] = 1; dfo[i] = ++c;
for(int e : G[i]) {
int v = A[e]^B[e]^i;
if(v == prt[i]) continue;
dep[v] = dep[i] + 1;
prt[v] = i;
predfs(v, c);
cnt[i] += cnt[v];
}
}
void dfsOne(int i, ll sum) {
if(Ans[1] < sum) Ans[1] = sum;
for(int e : G[i]) if(A[e] != prt[i])
dfsOne(B[e], sum - D[e] + C[e]);
}
void getAnsOne() {
{ int c = 0; predfs(1, c); }
for(int i = 1; i < N; i++) if(prt[A[i]] == B[i]) {
swap(A[i], B[i]);
swap(C[i], D[i]);
}
ll sum = 0;
for(int i = 1; i < N; i++) sum += D[i];
dfsOne(1, sum);
}
int main() {
ios::sync_with_stdio(false);
cin >> N;
for(int i = 1; i < N; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
G[A[i]].eb(i);
G[B[i]].eb(i);
Sum += C[i] + D[i];
}
getAnsOne();
cin >> Q;
for(int a; Q--;) {
cin >> a;
printf("%lld\n", Sum - Ans[a]);
}
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... |