이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
if(b==0)return 1;
if(b==1)return(a%mod);
int tem=po(a,b/2);
if(b&1)return(((tem*tem)%mod)*a)%mod;
else return(tem*tem)%mod;
}
int GCD(int a,int b){
int x=0;
int ra,rb;
while(a&&b){
if(((a&1)==0)&&((b&1)==0)){
a>>=1,b>>=1,x++;
}
else if((a^b)&1){
if(a&1)b>>=1;
else a>>=1;
}
else{
ra=abs(a-b),rb=min(a,b);
a=ra,b=rb;
}
}
return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
vector<pair<int,pii> > g[200010];
vector<int> v;
int n,p,s=0,fa[200010],o[200010],vl[200010],mv[200010],qr[200010],so[200010],in[200010],val[200010],mvl[200010];
pii vv[200010],rt;
bool rd[200010];
void dfs(int p,int f){
fa[p]=f;
for(pair<int,pii> pi:g[p]){
if(pi.X==f)continue;
dfs(pi.X,p);
}
}
int dfs1(int p,int f){
int re=-1;
for(pair<int,pii> pi:g[p]){
if(pi.X==f)continue;
int tr=dfs1(pi.X,p)+pi.Y.X;
if(tr<0)continue;
if(re==-1){
re=tr;
}
else{
if(tr>re)swap(tr,re);
v.pb(tr);
}
}
if(rd[p]){
if(re>=0)v.pb(re);
return -1e16;
}
else{
if(re<0)return 0;
return re;
}
}
void dfs2(int p,int f){
for(pair<int,pii> pi:g[p]){
if(pi.X==f)continue;
dfs2(pi.X,p);
vl[p]+=(vl[pi.X]+pi.Y.Y);
mv[pi.X]=vl[pi.X]+pi.Y.Y;
}
}
int dfs3(int p,int f){
int re=vl[p];
for(pair<int,pii> pi:g[p]){
if(pi.X==f)continue;
vl[pi.X]+=vl[p]-mv[pi.X]+pi.Y.X;
re=max(re,dfs3(pi.X,p));
}
return re;
}
pii dfs4(int p,int f){
pii tp={-1,-1},tpp={-1,-1};
for(pair<int,pii> pi:g[p]){
if(pi.X==f)continue;
pii tr=dfs4(pi.X,p);
tr.X+=pi.Y.X;
if(tr.X>=tp.X){
swap(tp.X,tp.Y);
swap(tpp.X,tpp.Y);
tp.X=tr.X;
tpp.X=tr.Y;
}
else if(tr.X>=tp.Y){
tp.Y=tr.X;
tpp.Y=tr.Y;
}
}
if(tp.X==-1){
return {0,p};
}
else if(tp.Y==-1){
if(o[2]>vl[p]-tp.X){
o[2]=vl[p]-tp.X;
rt={p,tpp.X};
}
return {tp.X,tpp.X};
}
else{
if(o[2]>vl[p]-tp.X-tp.Y){
o[2]=vl[p]-tp.X-tp.Y;
rt={tpp.X,tpp.Y};
bug(p,vl[p],tp.X,tp.Y,tpp.X,tpp.Y);
}
return {tp.X,tpp.X};
}
}
void solve1(){
memres(vl);
memres(mv);
dfs2(0,-1);
int x=dfs3(0,-1);
o[1]=s-x;
}
void solve2(){
o[2]=1e16;
F(n)vl[i]=s-vl[i];
dfs4(0,-1);
}
signed main(){
IOS();
cin>>n;
F(n-1){
int x,y,a,b;
cin>>x>>y>>a>>b;
s+=(a+b);
--x,--y;
g[x].pb({y,{a,b}});
g[y].pb({x,{b,a}});
in[x]++,in[y]++;
}
int q;
cin>>q;
F(q)cin>>qr[i];
solve1();
solve2();
int p=rt.X,pp=rt.Y;
bug(p,pp);
dfs(p,-1);
int tp=pp;
while(tp!=-1){
if(fa[tp]!=-1)so[fa[tp]]=tp;
rd[tp]=1;
tp=fa[tp];
}
dfs1(p,-1);
int ct=0;
F(n)if(sz(g[i])==1)ct++;
sort(all(v));
int ms=0;
for(int i=ct-1;i>=2;i--){
ms+=v[ct-1-i];
bug(v[ct-1-i],sz(v),ct);
o[i]=ms;
}
F(q){
if(qr[i]>=ct)cout<<0<<endl;
else cout<<o[qr[i]]<<endl;
}
return 0;
}
# | 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... |