#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__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...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e5+5;
vector<pii> g[maxn]; // to, value
int up[maxn], updown[maxn], par[maxn];
ll sigup[maxn];
pii deep[maxn]; // dep, where
int dep[maxn];
ll RT = inf;
int p1, p2;
ll all[maxn], L[maxn], R[maxn];
void dfs1(int v, int p) {
par[v] = p;
for (pii u : g[v]) {
if (u.f != p) {
updown[u.f] = u.s;
dfs1(u.f, v);
}
else up[v] = u.s;
}
}
void dfs2(int v, int p) {
for (pii u : g[v]) {
if (u.f != p) {
dep[u.f] = dep[v] + up[u.f];
dfs2(u.f, v);
sigup[v] += sigup[u.f] + up[u.f];
}
}
}
void dfs3(int v, int p) {
if (p != -1) all[v] = all[p] - up[v] + updown[v];
else all[v] = sigup[v];
vector<pii>here; here.pb({dep[v], v});
for (pii u : g[v]) {
if (u.f != p) {
dfs3(u.f,v);
here.pb(deep[u.f]);
}
}
sort(ALL(here), greater<pii>());
if (SZ(here) > 1) {
ll df = all[v] - here[0].f - here[1].f + dep[v]*2;
bug(here[0].f, here[1].f, here[0].s, here[1].s);
if (df < RT) {
RT = df;
p1 = here[0].s; p2 = here[1].s;
}
}
deep[v] = here[0];
}
pii s[maxn*4];
ll tg[maxn*4];
bool rem[maxn];
void push(int o, int l, int r){
if (tg[o]) {
s[o].f += tg[o];
if (l!=r) {
tg[o*2] += tg[o];
tg[o*2+1] += tg[o];
}
tg[o] = 0;
}
}
void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) {
push(o,l,r);
if (l>R || r<L) return;
if (l >= L && r <= R) {
tg[o] += v;
push(o,l,r);
return;
}
int mid = (l+r)/2;
MO(L,R,v,o*2,l,mid);
MO(L,R,v,o*2+1,mid+1,r);
s[o] = max(s[o*2], s[o*2+1]);
}
void MOpt(int p, pii v, int o=1, int l=0, int r=maxn-1) {
if (l>p || r<p) return;
if (l == r) {
s[o] = v;
return;
}
int mid = (l+r)/2;
MOpt(p,v,o*2,l,mid);
MOpt(p,v,o*2+1,mid+1,r);
s[o] = max(s[o*2], s[o*2+1]);
}
int IT = 0;
void dfs4(int v, int p) {
L[v] = R[v] = IT++;
for (pii u : g[v]) {
if (u.f != p) {
dfs4(u.f,v);
R[v] = R[u.f];
}
}
}
ll ans[maxn];
void clr(int v) {
while (!rem[v]) {
rem[v] = 1;
int p = par[v];
MO(L[v], R[v], -up[v]);
v = p;
}
}
signed main(){
IOS();
int n; cin>>n;
REP(i,n-1) {
int a,b,c,d; cin>>a>>b>>c>>d; swap(c,d);
g[a].pb({b,c});
g[b].pb({a,d});
}
dfs1(1,-1); dfs2(1,-1); dfs3(1,-1);
memset(ans, 0x3f, sizeof ans);
REP1(i,n) {
bug(i, up[i], dep[i], sigup[i], all[i]);
MN(ans[1], all[i]);
}
bug(RT, p1, p2);
ans[2] = RT;
dep[p1] = up[p1] = 0;
dfs1(p1, -1); dfs2(p1, -1); dfs4(p1, -1);
rem[p1] = 1;
REP1(i,n) {
bug(i, L[i], dep[i], up[i]);
MOpt(L[i], {dep[i], i});
}
bug(s[1].f, s[1].s, dep[p2]);
clr(p2);
for (int k = 3; k<=n; ++k) {
pii hi = s[1];
bug (hi.f, hi.s);
RT -= hi.f;
clr(hi.s);
ans[k] = RT;
}
int qq; cin>>qq;
while (qq--) {
int x; cin>>x;
cout<<ans[x]<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6604 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6604 KB |
Output is correct |
| 2 |
Correct |
429 ms |
30500 KB |
Output is correct |
| 3 |
Correct |
706 ms |
59508 KB |
Output is correct |
| 4 |
Correct |
520 ms |
35768 KB |
Output is correct |
| 5 |
Correct |
424 ms |
31656 KB |
Output is correct |
| 6 |
Correct |
448 ms |
36372 KB |
Output is correct |
| 7 |
Correct |
331 ms |
31704 KB |
Output is correct |
| 8 |
Correct |
550 ms |
57072 KB |
Output is correct |
| 9 |
Correct |
372 ms |
34700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6604 KB |
Output is correct |
| 2 |
Incorrect |
455 ms |
31304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6604 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6604 KB |
Output is correct |
| 2 |
Correct |
429 ms |
30500 KB |
Output is correct |
| 3 |
Correct |
706 ms |
59508 KB |
Output is correct |
| 4 |
Correct |
520 ms |
35768 KB |
Output is correct |
| 5 |
Correct |
424 ms |
31656 KB |
Output is correct |
| 6 |
Correct |
448 ms |
36372 KB |
Output is correct |
| 7 |
Correct |
331 ms |
31704 KB |
Output is correct |
| 8 |
Correct |
550 ms |
57072 KB |
Output is correct |
| 9 |
Correct |
372 ms |
34700 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6604 KB |
Output is correct |
| 11 |
Incorrect |
455 ms |
31304 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6604 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
