#include <bits/stdc++.h>
using namespace std ;
const int MAX = 2e5 + 10 ;
int arr[MAX] ;
int n , q ;
vector< vector< pair<int , int> > >adj(MAX) ;
long long ans[MAX] ;
int mark[MAX] ;
int sz[MAX] ;
int cursrc , cursz ;
long long curcost ;
pair<long long , int>tree[4 * MAX] ;
long long lazy[4 * MAX] ;
void build(int node , int l , int r)
{
if(l == r)
{
tree[node] = {0 , l} , lazy[node] = 0 ;
return ;
}
int mid = (l + r) >> 1 ;
build(node << 1 , l , mid) ;
build(node << 1 | 1 , mid+1 , r) ;
tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
void prop(int node , int l , int r)
{
tree[node].first += lazy[node] ;
if(l != r)
{
lazy[node << 1] += lazy[node] ;
lazy[node << 1 | 1] += lazy[node] ;
}
lazy[node] = 0 ;
}
void update(int node , int l , int r , int from , int to , int val)
{
prop(node , l , r) ;
if(from > r || to < l || from > to)
return ;
if(l >= from && r <= to)
{
lazy[node] += val ;
prop(node , l , r) ;
return ;
}
int mid = (l + r) >> 1 ;
update(node << 1 , l , mid , from , to , val) ;
update(node << 1 | 1 , mid+1 , r , from , to , val) ;
tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
pair<long long , int>query(int node , int l , int r , int from , int to)
{
prop(node , l , r) ;
if(from > r || to < l || from > to)
return {-1e18 , -1e9} ;
if(l >= from && r <= to)
return tree[node] ;
int mid = (l + r) >> 1 ;
pair<long long , int>a = query(node << 1 , l , mid , from , to) ;
pair<long long , int>b = query(node << 1 | 1 , mid+1 , r , from , to) ;
return max(a , b) ;
}
void dfs_pre(int node , int par)
{
sz[node] = 1 ;
for(auto &childd : adj[node])
{
int child = childd.first ;
if(child == par || mark[child])
continue ;
dfs_pre(child , node) ;
sz[node] += sz[child] ;
}
}
int FindCentroid(int node , int par)
{
for(auto &childd : adj[node])
{
int child = childd.first ;
if(child == par || mark[child])
continue ;
if(sz[child] > cursz / 2)
return FindCentroid(child , node) ;
}
return node ;
}
int val[MAX] ;
int in[MAX] , out[MAX] ;
int tim = 0 ;
int sub[MAX] , P[MAX] , erased[MAX] , edgcost[MAX] ;
long long sum[MAX] ;
void dfs(int node , int par)
{
in[node] = ++tim , P[node] = par ;
curcost += val[node] , erased[node] = 0 ;
sum[node] = val[node] ;
for(auto &childd : adj[node])
{
int child = childd.first , w = childd.second ;
if(child == par)
edgcost[node] = w ;
if(child == par || mark[child])
continue ;
val[child] = w ;
if(in[node] == 1) //centroid
sub[child] = child ;
else
sub[child] = sub[node] ;
dfs(child , node) ;
sum[node] += sum[child] ;
}
out[node] = tim ;
update(1 , 1 , cursz , in[node] , out[node] , val[node]) ;
}
void Erase(int node)
{
while((!erased[node]) && node)
{
erased[node] = 1 ;
update(1 , 1 , cursz , in[node] , out[node] , -1 * val[node]) ;
node = P[node] ;
}
}
void solve(int src , long long cost)
{
cursrc = src , curcost = cost ;
dfs_pre(src , 0) ;
cursz = sz[src] ;
int centroid = FindCentroid(src , -1) ;
val[centroid] = 0 ;
build(1 , 1 , cursz) ;
dfs(centroid , 0) ;
ans[1] = min(ans[1] , curcost) ;
bool flag = true ;
int prv ;
for(int i = 1 ; i <= cursz ; ++i)
{
pair<long long , int>p = query(1 , 1 , cursz , 1 , cursz) ;
if((!p.first))
{
ans[i] = min(ans[i] , ans[i-1]) ;
continue ;
}
int node = p.second ;
if(i > 1)
flag &= (sub[node] == sub[prv]) ;
curcost -= p.first , Erase(node) ;
if(!flag)
ans[i] = min(ans[i] , curcost) ;
else if(i > 1)
ans[i] = min(ans[i] , curcost + p.first - max(query(1 , 1 , n , 1 , in[sub[node]]-1).first , query(1 , 1 , n , out[sub[node]]+1 , n).first)) ;
prv = node ;
}
mark[centroid] = 1 ;
for(auto &childd : adj[centroid])
{
int child = childd.first , w = childd.second ;
if(mark[child])
continue ;
solve(child , cost + sum[centroid] - sum[child] + edgcost[child]) ;
}
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 0 ; i < n-1 ; ++i)
{
int x , y , c , d ;
cin>>x>>y>>c>>d ;
adj[x].emplace_back(y , c) ;
adj[y].emplace_back(x , d) ;
}
for(int i = 0 ; i <= n ; ++i)
ans[i] = 1e18 ;
solve(1 , 0) ;
cin>>q ;
while(q--)
{
int x ;
cin>>x ;
cout<<ans[x]<<"\n" ;
}
return 0 ;
}
Compilation message
designated_cities.cpp: In function 'void solve(int, long long int)':
designated_cities.cpp:175:30: warning: unused variable 'w' [-Wunused-variable]
175 | int child = childd.first , w = childd.second ;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
589 ms |
41228 KB |
Output is correct |
| 3 |
Correct |
895 ms |
52852 KB |
Output is correct |
| 4 |
Correct |
568 ms |
39844 KB |
Output is correct |
| 5 |
Correct |
346 ms |
41212 KB |
Output is correct |
| 6 |
Correct |
713 ms |
42932 KB |
Output is correct |
| 7 |
Correct |
317 ms |
41356 KB |
Output is correct |
| 8 |
Correct |
1040 ms |
53348 KB |
Output is correct |
| 9 |
Correct |
253 ms |
41808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
589 ms |
41228 KB |
Output is correct |
| 3 |
Correct |
895 ms |
52852 KB |
Output is correct |
| 4 |
Correct |
568 ms |
39844 KB |
Output is correct |
| 5 |
Correct |
346 ms |
41212 KB |
Output is correct |
| 6 |
Correct |
713 ms |
42932 KB |
Output is correct |
| 7 |
Correct |
317 ms |
41356 KB |
Output is correct |
| 8 |
Correct |
1040 ms |
53348 KB |
Output is correct |
| 9 |
Correct |
253 ms |
41808 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
