#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, pair<int, int> > > adj[200005];
int ans[200005], sumsum, cnt;
void dfs1(unordered_map<int, int> &mp, vector<int> &sz, int u, int p)
{
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
if (v==p || !mp[v])
continue;
dfs1(mp, sz, v, u);
sz[mp[u]]+=sz[mp[v]];
}
}
int dfs2(unordered_map<int, int> &mp, vector<int> &sz, int u, int p, int n)
{
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
if (v==p || !mp[v])
continue;
if (sz[mp[v]]*2>n)
return dfs2(mp, sz, v, u, n);
}
return u;
}
vector<int> *dfs3(unordered_map<int, int> &mp, int u, int p)
{
vector<int> *ans=new vector<int>;
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second.first;
if (v==p || !mp[v])
continue;
vector<int> *res=dfs3(mp, v, u);
(*res)[0]+=w;
if (ans->size()<res->size())
swap(ans, res);
if (res->empty())
{
delete res;
continue;
}
if ((*ans)[0]<(*res)[0])
swap((*ans)[0], (*res)[0]);
for (int x:*res)
ans->push_back(x);
delete res;
}
if (ans->empty())
ans->push_back(0);
//cout << u << ": ";
//for (int x:*ans)
// cout << x << ' ';
//cout << '\n';
return ans;
}
void dfs4(unordered_map<int, int> &mp, vector<int> &sum, int u, int p)
{
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second.first;
if (v==p || !mp[v])
continue;
dfs4(mp, sum, v, u);
sum[mp[u]]+=sum[mp[v]]+w;
}
}
void dfs5(unordered_map<int, int> &mp, vector<int> &tmp, int u, int p)
{
//cout << "dfs5 " << u << '\n';
tmp.push_back(u);
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
if (v==p || !mp[v])
continue;
dfs5(mp, tmp, v, u);
}
}
void recur(vector<int> &vec, int offset)
{
int n=vec.size();
if (n<=2)
return;
//cout << "recur ";
//for (int x:vec)
// cout << x << ' ';
//cout << '\n';
unordered_map<int, int> mp;
vector<pair<int, int> > dp;
vector<int> sum(n+1, 0), sz(n+1, 1);
for (int i=0; i<n; i++)
mp[vec[i]]=i+1;
dfs1(mp, sz, vec[0], 0);
int centroid=dfs2(mp, sz, vec[0], 0, n);
//cout << "centroid = " << centroid << '\n';
for (int i=0; i<adj[centroid].size(); i++)
{
int v=adj[centroid][i].first, w=adj[centroid][i].second.first;
if (!mp[v])
continue;
vector<int> *res=dfs3(mp, v, centroid);
(*res)[0]+=w;
for (int x:*res)
dp.push_back({x, i});
delete res;
}
//cout << "here\n";
sort(dp.begin(), dp.end(), greater<pair<int, int> >());
dfs4(mp, sum, centroid, 0);
int cur=0, ind=0;
//cout << "dp: ";
//for (int i=0; i<dp.size(); i++)
//{
// cout << dp[i].first << ' ' << dp[i].second << '\n';
//}
for (int i=1; i<dp.size(); i++)
{
if (dp[i-1].second!=dp[i].second)
{
ind=i;
break;
}
}
//cout << "sum = " << sum[mp[centroid]] << '\n';
for (int i=2; i<=dp.size(); i++)
{
cur+=dp[i-2].first;
ans[i]=min(ans[i], sum[mp[centroid]]-cur-dp[max(ind, i-1)].first+offset);
}
//cout << "here\n";
for (int i=0; i<adj[centroid].size(); i++)
{
//cout << "i=" << i << '\n';
int v=adj[centroid][i].first, w1=adj[centroid][i].second.first, w2=adj[centroid][i].second.second;
if (!mp[v])
continue;
vector<int> tmp;
dfs5(mp, tmp, v, centroid);
recur(tmp, offset+sum[mp[centroid]]-sum[mp[v]]-w1+w2);
}
}
void calc1(int u, int p)
{
int leaf=1;
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second.first;
if (v==p)
continue;
calc1(v, u);
sumsum+=w;
leaf=0;
}
if (leaf)
cnt++;
}
void calc2(int u, int p, int offset)
{
ans[1]=min(ans[1], offset);
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w1=adj[u][i].second.first, w2=adj[u][i].second.second;
if (v==p)
continue;
calc2(v, u, offset-w1+w2);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n;
for (int i=1; i<n; i++)
{
int u, v, w1, w2;
cin >> u >> v >> w1 >> w2;
adj[u].push_back({v, {w1, w2}});
adj[v].push_back({u, {w2, w1}});
}
vector<int> tmp(n);
for (int i=1; i<=n; i++)
tmp[i-1]=i, ans[i]=1e18;
recur(tmp, 0);
calc1(1, 0);
calc2(1, 0, sumsum);
for (int i=cnt+1; i<=n; i++)
ans[i]=ans[cnt];
cin >> q;
for (int i=1; i<=q; i++)
{
int x;
cin >> x;
cout << ans[x] << '\n';
}
}
# | 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... |