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;
typedef long long ll;
const int MAXN=2e5+5;
vector<tuple<int, ll, ll> > g[MAXN];
pair<ll, int> mprof[MAXN][2];
pair<ll, int> seg[MAXN*4];
ll lz[MAXN*4];
ll dp[MAXN], respf[MAXN], ppai[MAXN], somaf;
int tini[MAXN], tfim[MAXN], tcara[MAXN], pai[MAXN];
bool marc[MAXN];
int n, q, raiz, contt;
void melhora(int cur, pair<ll, int> val) {
if(val.first>=mprof[cur][0].first) {
mprof[cur][1]=mprof[cur][0];
mprof[cur][0]=val;
}
else if(val.first>mprof[cur][1].first) {
mprof[cur][1]=val;
}
}
void predfs(int cur, int p) {
mprof[cur][0]={0, cur};
for(auto aresta : g[cur]) {
int viz; ll peso, rpeso;
tie(viz, peso, rpeso)=aresta;
if(viz==p) continue;
predfs(viz, cur);
dp[cur]+=dp[viz]+rpeso;
melhora(cur, {mprof[viz][0].first+peso, mprof[viz][0].second});
}
tfim[cur]=contt;
}
void gira(int cur, int p) {
respf[1]=max(respf[1], dp[cur]);
if(dp[cur]+mprof[cur][0].first>respf[2]) {
respf[2]=dp[cur]+mprof[cur][0].first;
raiz=cur;
}
// printf("dp[%d]= %lld // mprof[%d][0]= %lld, %d\n", cur, dp[cur], cur, mprof[cur][0].first, mprof[cur][0].second);
for(auto aresta : g[cur]) {
int viz; ll peso, rpeso;
tie(viz, peso, rpeso)=aresta;
if(viz==p) continue;
ll dpc=dp[cur], dpv=dp[viz];
auto mprofc0=mprof[cur][0], mprofc1=mprof[cur][1];
auto mprofv0=mprof[viz][0], mprofv1=mprof[viz][1];
dp[cur]-=(dp[viz]+rpeso);
dp[viz]+=(dp[cur]+peso);
if(mprof[cur][0].second==mprof[viz][0].second) mprof[cur][0]=mprof[cur][1];
melhora(viz, {mprof[cur][0].first+rpeso, mprof[cur][0].second});
gira(viz, cur);
dp[cur]=dpc; dp[viz]=dpv;
mprof[cur][0]=mprofc0; mprof[cur][1]=mprofc1;
mprof[viz][0]=mprofv0; mprof[viz][1]=mprofv1;
}
}
void refresh(int sind, int ini, int fim) {
seg[sind].first+=lz[sind];
if(ini==fim) {
lz[sind]=0;
seg[sind].second=tcara[ini];
return;
}
int e=sind*2; int d=e+1;
lz[e]+=lz[sind];
lz[d]+=lz[sind];
lz[sind]=0;
}
void update(int sind, int ini, int fim, int qini, int qfim, ll val) {
refresh(sind, ini, fim);
if(qini>fim||qfim<ini) return;
if(qini<=ini&&qfim>=fim) {
lz[sind]+=val;
refresh(sind, ini, fim);
return;
}
int m=(ini+fim)/2; int e=sind*2; int d=e+1;
update(e, ini, m, qini, qfim, val);
update(d, m+1, fim, qini, qfim, val);
seg[sind]=max(seg[e], seg[d]);
}
void dfs(int cur, int p, ll d) {
tini[cur]=++contt;
for(auto aresta : g[cur]) {
int viz; ll peso, rpeso;
tie(viz, peso, rpeso)=aresta;
if(viz==p) continue;
dfs(viz, cur, d+peso);
pai[viz]=cur;
ppai[viz]=peso;
}
tfim[cur]=contt;
tcara[tini[cur]]=cur;
update(1, 1, n, tini[cur], tini[cur], d);
// printf("update %d +%lld\n", tini[cur], d);
}
void pinta(int cur) {
while(!marc[cur]) {
marc[cur]=1;
update(1, 1, n, tini[cur], tfim[cur], -ppai[cur]);
cur=pai[cur];
}
}
int main() {
scanf("%d", &n);
for(int i=1; i<n; i++) {
int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
g[a].push_back({b, c, d}); g[b].push_back({a, d, c});
somaf+=c; somaf+=d;
}
predfs(1, 1);
gira(1, 1);
dfs(raiz, raiz, 0);
marc[raiz]=1;
pinta(seg[1].second);
// for(int i=1; i<=n; i++) printf("%d >> %d %d >> %lld %d\n", i, tini[i], tfim[i], ppai[i], pai[i]);
for(int i=3; i<=n; i++) {
respf[i]=respf[i-1]+seg[1].first;
int cara=seg[1].second;
pinta(cara);
// printf("%d usa %d\n", i, cara);
}
scanf("%d", &q);
while(q--) {
int val; scanf("%d", &val);
printf("%lld\n", somaf-respf[val]);
}
}
Compilation message (stderr)
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
designated_cities.cpp:121:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
designated_cities.cpp:143:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int val; scanf("%d", &val);
~~~~~^~~~~~~~~~~~
# | 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... |