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>
using namespace std;
#define int long long
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
const int N = 3e5 + 10;
const int INF = 1e18 + 10;
const int mod = 1e9 + 7;
int n;
vector<pair<int , pair<int , int>>> g[N];
int ans[N];
int dp[N];
int dw[N];
int up[N];
vector<int> pre[N];
vector<int> suf[N];
int pos[N];
void efs(int v , int pr) {
for(auto [u , w] : g[v]) if(u != pr) {
efs(u , v);
dp[v] += dp[u] + w.S;
}
}
int root;
void rer(int v , int pr) {
ans[1] = max(ans[1] , dp[v]);
// cout << v << " : " << dp[v] << " " << max(dw[v] , up[v]) << " tet\n";
if(ans[2] < dp[v] + max(dw[v] , up[v])) {ans[2] = dp[v] + max(dw[v] , up[v]) , root = v;}
for(auto [u , w] : g[v]) if(u != pr) {
dp[v] -= dp[u] + w.S;
dp[u] += dp[v] + w.F;
rer(u , v);
dp[u] -= dp[v] + w.F;
dp[v] += dp[u] + w.S;
}
}
void kfs(int v , int pr) {
for(auto [u , w] : g[v]) if(u != pr) {
kfs(u , v);
dw[v] = max(dw[v] , dw[u] + w.F);
pos[u] = pre[v].size();
pre[v].pb(dw[v]);
}
for(int i = g[v].size()-1 ; ~i ; i--) {
int u = g[v][i].F;
auto w = g[v][i].S;
if(u == pr) continue;
int x = dw[u] + w.F;
if(suf[v].size()) suf[v].pb(max(suf[v].back() , x));
else suf[v].pb(x);
}
reverse(all(suf[v]));
}
void lfs(int v , int pr) {
for(auto [u , w] : g[v]) if(u != pr) {
up[u] = up[v];
int p = pos[u];
if(p != 0) up[u] = max(up[u] , pre[v][p-1]);
if(p != suf[v].size() - 1) up[u] = max(up[u] , suf[v][p+1]);
up[u] += w.S;
lfs(u , v);
}
}
multiset<int> s[N];
void dfs(int v , int pr) {
s[v].insert(0);
for(auto [u , w] : g[v]) if(u != pr) {
dfs(u , v);
int x = *(--s[u].end());
s[u].erase(--s[u].end());
s[u].insert(x + w.F);
if(s[u].size() > s[v].size()) s[v].swap(s[u]);
for(auto p : s[u]) s[v].insert(p);
}
// cout << v << " :\n";
// for(auto x : s[v]) cout << x << " ";
// cout << "\n";
}
void solve() {
cin >> n;
if(n == 2) {
int x , y;
cin >> x >> y >> x >> y;
int q;
cin >> q;
while(q--) {
int z;
cin >> z;
if(z == 1) cout << min(x , y) << "\n";
else cout << "0\n";
}
return;
}
int f = 0;
for(int i = 1 ; i < n ; i++) {
int v , u , a , b;
cin >> v >> u >> a >> b; f += a + b;
g[v].pb({u , {a , b}});
g[u].pb({v , {b , a}});
}
// cout << "\n";
kfs(1 , -1);
lfs(1 , -1);
// for(int i = 1 ; i <= n ; i++)
// cout << i << " " << dw[i] << " " << up[i] << "\n";
efs(1 , -1);
ans[1] = dp[1];
rer(1 , -1);
ans[1] = ans[1];
ans[2] = ans[2];
dfs(root , -1);
// cout << root << "\n";
int q;
cin >> q;
int p = 3;
s[root].erase(--s[root].end());
while(s[root].size())
ans[p] = ans[p-1] + *(--s[root].end()) , p++ , s[root].erase(--s[root].end());
while(q--) {
int x;
cin >> x;
cout << f - ans[x] << "\n";
}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2
5
1 2 1 2
2 3 2 3
3 4 3 4
4 5 4 5
5
1 2 3 4 5
*/
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
Compilation message (stderr)
designated_cities.cpp: In function 'void lfs(long long int, long long int)':
designated_cities.cpp:74:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if(p != suf[v].size() - 1) up[u] = max(up[u] , suf[v][p+1]);
| ~~^~~~~~~~~~~~~~~~~~~~
# | 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... |