#include <bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=200020;
const ll INF=1000000000000000001;
typedef struct line{
int s, e;
ll val;
}line;
int N, Q;
map <int, ll> v[mxN];
vector <pll> rv[mxN];
ll ans[mxN];
ll tot, rtot;
ll dep[mxN], rdep[mxN];
void dfs(int now, int pre)
{
for(auto iter=v[now].begin();iter!=v[now].end();iter++)
{
if(iter->fir==pre) continue;
int nxt=iter->fir;
dep[nxt]=dep[now]+iter->sec;
tot+=iter->sec;
dfs(nxt, now);
}
}
void rdfs(int now, int pre)
{
for(pll ele : rv[now])
{
if(ele.fir==pre) continue;
rdep[ele.fir]=rdep[now]+ele.sec;
rdfs(ele.fir, now);
}
}
void solv1()
{
dfs(1, -1);
rdfs(1, -1);
for(int i=1;i<=N;i++)
{
ans[1]=max(ans[1], tot-dep[i]+rdep[i]);
}
ans[1]=rtot-ans[1];
}
typedef struct cmp1{
bool operator()(const pll a, const pll b) const
{
if(a.sec!=b.sec) return a.sec<b.sec;
return a.fir<b.fir;
}
}cmp1;
set <pll, cmp1> pq;
void solv2()
{
for(int i=1;i<=N;i++)
{
if(v[i].size()==2)
{
ll a=-1, b=-1, ia, ib, ai, bi;
for(auto iter=v[i].begin();iter!=v[i].end();iter++)
{
if(a==-1) a=iter->fir, ia=iter->sec;
else b=iter->fir, ib=iter->sec;
}
auto itera=v[a].find(i);
ai=itera->sec;
v[a].erase(itera);
auto iterb=v[b].find(i);
bi=iterb->sec;
v[b].erase(iterb);
v[a].insert({b, ai+ib});
v[b].insert({a, bi+ia});
}
}
for(int i=1;i<=N;i++)
{
if(v[i].size()==1)
{
auto iter=v[i].begin();
pq.insert({i, iter->sec});
}
}
int pqs=pq.size();
for(int i=pqs;i<=N;i++) ans[i]=0;
for(int i=pqs-1;i>=2;i--)
{
if(pq.empty()) return;
pll now=*pq.begin();
pq.erase(pq.begin());
ans[i]=ans[i+1]+now.sec;
auto iter=v[now.fir].begin();
int nxt=iter->fir;
auto itern=v[nxt].find(now.fir);
v[nxt].erase(itern);
if(i==2) break;
if(v[nxt].size()==2)
{
ll a=-1, b=-1, ia, ib, ai, bi;
for(auto iter=v[nxt].begin();iter!=v[nxt].end();iter++)
{
if(a==-1) a=iter->fir, ia=iter->sec;
else b=iter->fir, ib=iter->sec;
}
if(v[a].size()==1)
{
ll nval=v[a].begin()->sec;
pq.erase({a, nval});
}
if(v[b].size()==1)
{
ll nval=v[b].begin()->sec;
pq.erase({b, nval});
}
auto itera=v[a].find(i);
auto iterb=v[b].find(i);
ai=itera->sec, bi=iterb->sec;
v[a].erase(itera); v[b].erase(iterb);
v[a].insert({b, ai+ib});
v[b].insert({a, bi+ia});
if(v[a].size()==1) pq.insert({a, v[a].begin()->sec});
if(v[b].size()==1) pq.insert({b, v[b].begin()->sec});
}
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
for(int i=0;i<N-1;i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
v[a].insert({b, d}); v[b].insert({a, c});
rv[a].push_back({b, c}); rv[b].push_back({a, d});
rtot+=c; rtot+=d;
}
solv1();
solv2();
cin >> Q;
while(Q--)
{
int a;
cin >> a;
cout << ans[a] << '\n';
}
}
Compilation message
designated_cities.cpp: In function 'void solv2()':
designated_cities.cpp:122:31: warning: 'ib' may be used uninitialized in this function [-Wmaybe-uninitialized]
122 | v[a].insert({b, ai+ib});
| ~~^~~
designated_cities.cpp:123:31: warning: 'ia' may be used uninitialized in this function [-Wmaybe-uninitialized]
123 | v[b].insert({a, bi+ia});
| ~~^~~
designated_cities.cpp:75:31: warning: 'ib' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | v[a].insert({b, ai+ib});
| ~~^~~
designated_cities.cpp:76:31: warning: 'ia' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | v[b].insert({a, bi+ia});
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14444 KB |
Output is correct |
| 2 |
Runtime error |
29 ms |
29036 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14444 KB |
Output is correct |
| 2 |
Runtime error |
555 ms |
119020 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14444 KB |
Output is correct |
| 2 |
Runtime error |
557 ms |
119080 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14444 KB |
Output is correct |
| 2 |
Runtime error |
29 ms |
29036 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14444 KB |
Output is correct |
| 2 |
Runtime error |
555 ms |
119020 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14444 KB |
Output is correct |
| 2 |
Runtime error |
29 ms |
29036 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
