#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;
int n, q, comp[maxn], mark[maxn], ans[maxn], pai[maxn], blk[maxn], sz[maxn], dw[maxn], up[maxn];
pair<int,int> dp[maxn];
vector<pair<pair<int,int>,pair<int,int>>> edg;
vector<int> vert, g[maxn], vertcent;
void dfsdeep(int u, int ant, int val) {
vert.pb(u);
pai[u] = ant;
dp[u] = mp(val,u);
for(auto id : g[u]) {
int v = u^edg[id].fr.fr^edg[id].fr.sc;
if(v == ant || blk[v]) continue;
int w;
if(edg[id].fr.fr == u) w = edg[id].sc.fr;
else w = edg[id].sc.sc;
if(ant == 0)
comp[v] = v;
else
comp[v] = comp[u];
dfsdeep(v,u,w);
dp[u] = max(dp[u],mp(dp[v].fr+val,dp[v].sc));
}
}
void sol(int rt) {
vert.clear();
dfsdeep(rt,0,0);
vector<pair<int,int>> deeps;
//pego eu mesmo e os melhores dos outros
for(auto v : vert) {
mark[v] = 0;
deeps.pb(mp(dp[v].fr,v));
// cout << rt << " -" << dp[v].fr << " " << v << endl;
}
sort(all(deeps),greater<pair<int,int>>());
int qtdc = 1;
int ans1 = dw[rt]+up[rt];
ans[1] = max(ans[1],ans1);
for(auto X : deeps) {
int v = X.sc;
if(mark[v]) continue;
ans1+= dp[v].fr;
qtdc++;
ans[qtdc] = max(ans[qtdc],ans1);
v = dp[v].sc;
// cout << rt << " -- " << v << " " << X.fr << endl;
while(v != 0 && mark[v] == 0) {
mark[v] = 1;
v = pai[v];
}
}
//obriga a escolher de subs diferentes
ans1 = dw[rt]+up[rt];
qtdc = 1;
for(auto v : vert) {
mark[v] = 0;
}
int v1 = dp[rt].sc;
ans1+= dp[rt].fr;
int comp1 = comp[v1];
while(v1 != 0 && mark[v1] == 0) {
mark[v1] = 1;
v1 = pai[v1];
}
for(auto X : deeps) {
int v = X.sc;
if(mark[v] || comp[dp[v].sc] == comp1) continue;
ans1+= dp[v].fr;
qtdc++;
ans[qtdc] = max(ans[qtdc],ans1);
v = dp[v].sc;
// cout << rt << " " << v << " " << X.fr << " " << qtdc << endl;
while(v != 0 && mark[v] == 0) {
mark[v] = 1;
v = pai[v];
}
break;
}
for(auto X : deeps) {
int v = X.sc;
if(mark[v]) continue;
ans1+= dp[v].fr;
qtdc++;
ans[qtdc] = max(ans[qtdc],ans1);
v = dp[v].sc;
// cout << rt << " -- " << v << " " << X.fr << endl;
while(v != 0 && mark[v] == 0) {
mark[v] = 1;
v = pai[v];
}
}
}
void dfscent(int u, int ant) {
vertcent.pb(u);
sz[u] = 1;
for(auto id : g[u]) {
int v = edg[id].fr.fr^edg[id].fr.sc^u;
if(blk[v] || v == ant) continue;
dfscent(v,u);
sz[u]+=sz[v];
}
}
void findcent(int rt) {
vertcent.clear();
dfscent(rt,0);
int ct;
for(auto u : vertcent) {
bool ok = true;
if(sz[rt]-sz[u] > sz[rt]/2) ok = false;
for(auto id : g[u]) {
int v = edg[id].fr.fr^edg[id].fr.sc^u;
if(blk[v] || sz[v] > sz[u]) continue;
if(sz[v] > sz[rt]/2) ok = false;
}
if(ok) ct = u;
}
sol(ct);
blk[ct] = 1;
for(auto id : g[ct]) {
int v = edg[id].fr.fr^edg[id].fr.sc^ct;
if(blk[v]) continue;
findcent(v);
}
}
void dfsdw(int u, int ant) {
dw[u] = 0;
for(auto id : g[u]) {
int v = u^edg[id].fr.fr^edg[id].fr.sc;
if(v == ant) continue;
int wdw,wup;
if(u == edg[id].fr.fr) {
wdw = edg[id].sc.fr;
wup = edg[id].sc.sc;
}
else {
wdw = edg[id].sc.sc;
wup = edg[id].sc.fr;
}
dfsdw(v,u);
dw[u]+=dw[v]+wup;
}
}
void dfsup(int u, int ant) {
for(auto id : g[u]) {
int v = u^edg[id].fr.fr^edg[id].fr.sc;
if(v == ant) continue;
int wdw,wup;
if(u == edg[id].fr.fr) {
wdw = edg[id].sc.fr;
wup = edg[id].sc.sc;
}
else {
wdw = edg[id].sc.sc;
wup = edg[id].sc.fr;
}
up[v] = up[u]+dw[u]-dw[v]-wup+wdw;
dfsup(v,u);
}
}
void solve() {
cin >> n;
for(int i = 0; i < n-1; i++) {
int u,v,w1,w2;
cin >> u >> v >> w1 >> w2;
g[u].pb(i);
g[v].pb(i);
ans[0]+= w1+w2;
edg.pb(mp(mp(u,v),mp(w1,w2)));
}
dfsdw(1,0);
dfsup(1,0);
// for(int i = 1; i <= n; i++) {
// cout << i << " " << dw[i] << " " << up[i] << endl;
// }
// findcent(1);
for(int i = 1; i <= n; i++) sol(i);
for(int i = 2; i <= n; i++) {
ans[i] = max(ans[i],ans[i-1]);
}
cin >> q;
while(q--) {
int x; cin >> x;
cout << ans[0]-ans[x] << endl;
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
Compilation message
designated_cities.cpp: In function 'void dfsdw(long long int, long long int)':
designated_cities.cpp:156:13: warning: variable 'wdw' set but not used [-Wunused-but-set-variable]
156 | int wdw,wup;
| ^~~
designated_cities.cpp: In function 'void findcent(long long int)':
designated_cities.cpp:130:9: warning: 'ct' may be used uninitialized in this function [-Wmaybe-uninitialized]
130 | int ct;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
2083 ms |
39020 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
2071 ms |
38916 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
2083 ms |
39020 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
