#include<bits/stdc++.h>
using namespace std;
const long long maxn=2000+10;
struct yal{
long long u,v,wu,wv,jam;
long long getad(long long fu){
if(fu==u){
return v;
}
return u;
}
long long getval(long long fu){
if(fu==u){
return wu;
}
return wv;
}
}alle[maxn];
vector<long long>adj[maxn],now;
long long resr[maxn][maxn],kaf=0,res[maxn],suma,n,cnt=0,val[maxn];
set<pair<long long,long long>>dp[maxn];
void merge(long long u,long long v){
long long fu=u;
if((long long)dp[u].size()<(long long)dp[v].size()){
swap(u,v);
}
for(auto x:dp[v]){
dp[u].insert(x);
}
if(fu!=u){
swap(dp[fu],dp[u]);
}
}
long long dfs(long long u,long long p=-1,long long len=0){
// dp[u].clear();
// if(p!=-1){
// dp[u].insert(make_pair(0,u));
// }
val[u]=0;
long long mx=0,rt=u;
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(v!=p){
kaf+=alle[x].getval(u);
int z=dfs(v,u,alle[x].getval(v));
// merge(u,v);
if(val[z]>=mx){
rt=z;
mx=val[z];
}
}
}
// auto x=*dp[u].rbegin();
// dp[u].erase(x);
// x.first+=len;
// dp[u].insert(x);
val[rt]+=len;
return rt;
}
void solve(long long u){
kaf=0;
dfs(u);
resr[u][0]=kaf;
vector<long long>tof;
for(int i=1;i<=n;i++){
tof.push_back(val[i]);
}
sort(tof.begin(),tof.end());
for(long long i=1;i<=n;i++){
resr[u][i]=resr[u][i-1];
if((long long)tof.size()>0){
resr[u][i]+=(tof.back());
tof.pop_back();
}
if(i==2){
if(res[i]<resr[u][i-1]){
now.clear();
now.push_back(u);
}
else if(res[i]==resr[u][i-1]){
now.push_back(u);
}
}
res[i]=max(res[i],resr[u][i-1]);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(long long i=0;i<n-1;i++){
cin>>alle[i].u>>alle[i].v>>alle[i].wv>>alle[i].wu;
alle[i].jam=alle[i].wu+alle[i].wv;
suma+=alle[i].wu+alle[i].wv;
adj[alle[i].u].push_back(i);
adj[alle[i].v].push_back(i);
}
for(long long i=1;i<=n;i++){
solve(i);
}
for(auto x:now){
long long f=1;
for(long long j=2;j<=n;j++){
if(resr[x][j-1]!=res[j]){
f=0;
}
}
if(f){
cnt++;
}
}
if(cnt>0){
assert(0);
}
long long q;
cin>>q;
for(long long i=1;i<=n;i++){
res[i]=suma-res[i];
}
for(long long i=0;i<q;i++){
long long d;
cin>>d;
cout<<res[d]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
