#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
struct yal{
int u,v,wu,wv,jam;
int getad(int fu){
if(fu==u){
return v;
}
return u;
}
int getval(int fu){
if(fu==u){
return wu;
}
return wv;
}
}alle[maxn];
vector<int>adj[maxn];
int n,val[maxn],res[maxn],suma=0,kaf=0,g;
void prea(int u=1,int p=-1){
for(auto x:adj[u]){
int v=alle[x].getad(u);
int wu=alle[x].getval(u);
if(v==p){
val[u]+=wu;
}
else{
val[1]+=wu;
val[v]-=wu;
prea(v,u);
}
}
}
void dfsa(int u=1,int p=-1){
if(p!=-1){
val[u]+=val[p];
}
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=p){
dfsa(v,u);
}
}
}
void aval(){
prea();
dfsa();
int mx=0;
for(int i=1;i<=n;i++){
if(val[i]>=mx){
res[1]=val[i];
mx=val[i];
g=i;
}
}
}
set<pair<int,int>>dp[maxn];
pair<int,int> getd(int u,int p=-1,int len=0){
pair<int,int>ret=make_pair(len,u);
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=p){
ret=max(ret,getd(v,u,len+alle[x].jam));
}
}
return ret;
}
void merge(int u,int v){
int fu=u;
if((int)dp[u].size()<(int)dp[v].size()){
swap(u,v);
}
for(auto x:dp[v]){
dp[u].insert(x);
}
if(fu!=u){
swap(dp[fu],dp[u]);
}
}
void dfs(int u,int p=-1,int len=0){
if(p!=-1){
dp[u].insert(make_pair(0,u));
}
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=p){
//cout<<"ha: "<<u<<" "<<v<<" "<<len<<endl;
kaf+=alle[x].getval(u);
dfs(v,u,alle[x].getval(v));
//cout<<"salam: "<<u<<" "<<v<<endl;
merge(u,v);
//cout<<"injy vas mas "<<u<<" "<<dp[u].size()<<" "<<v<<" "<<dp[v].size()<<endl;
}
}
auto x=*dp[u].rbegin();
dp[u].erase(x);
x.first+=len;
dp[u].insert(x);
}
void dovombebad(){
//int g=getd(1).second;
//cout<<"wtf: "<<g<<endl;
dfs(g);
//cout<<"nagooo"<<endl;
int ted=(int)dp[g].size();
res[2]=kaf;
//cout<<"by"<<ted<<endl;
for(int i=2;i<=ted;i++){
res[i]+=i!=2?res[i-1]:0+(*dp[g].rbegin()).first;
dp[g].erase(*dp[g].rbegin());
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
cin>>n;
for(int 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);
}
int q;
cin>>q;
aval();
if(n>1){
dovombebad();
}
for(int i=1;i<=n;i++){
res[i]=suma-res[i];
}
for(int i=0;i<q;i++){
int d;
cin>>d;
cout<<res[d]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
432 ms |
82312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
432 ms |
82312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
