(mathcal{Description})
Link.
给定一棵含 (n) 个结点的树，双向边权不相同。(q) 次询问，每次询问在树上标记 (e) 个点，标记的价值为所有趋向于某个标记点的有向边权值之和，求价值的最大值。
(qle nle2 imes10^5)。
(mathcal{Solution})
(e=1 ext{ or }2) 的时候可以直接换根求解。需要强调的是，当确定一个被标记的根时，其余标记点的贡献为根到这个标记点的有向路径长度（取并）。接下来引入一些结论。首先有：
对于一棵根被钦定标记的树（(e=1)），当 (e=k<n) 时，一定能通过标记深度最深的结点使得其成为 (e=k) 时的最优解。
不难意会。（
由此可以推出一个关键的结论：
对于 (k>2)，(e=k) 时的最优解必然通过在某个 (e=k-1) 时的最优解的基础上新标记一个点得到。
记 (e=k) 时某个最优解标记点集合为 (S)，(e=k+1) 时任一最优解的标记点集合为 (T)，考虑反证，若不存在 (Ssub T)：
- 若 (Scap T eqvarnothing)，取一个 (rin Scap T)，标记并作为树根。由上一个结论，矛盾。
- 若 (Scap T=varnothing)，考虑把 (T) 中的一个结点丢到 (S) 中，此时 (S) 不会比 (T) 劣。
所以，以 (e=2) 时的一个标记点为根，令每片叶子的权值为其保持作为子树最深点，向上能爬的距离。排序取前 (k) 大之和加上一些常数就是 (e=k) 的答案。复杂度 (mathcal O(nlog n))。
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <algorithm>
#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )
#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )
typedef long long LL;
typedef std::pair<int, LL> PIL;
inline int rint() {
int x = 0, s = getchar();
for ( ; s < '0' || '9' < s; s = getchar() );
for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
return x;
}
template<typename Tp>
inline void wint( Tp x ) {
if ( x < 0 ) putchar( '-' ), x = -x;
if ( 9 < x ) wint( x / 10 );
putchar( x % 10 ^ '0' );
}
inline LL lmax( const LL a, const LL b ) { return a < b ? b : a; }
inline void chkmax( LL& a, const LL b ) { a < b && ( a = b, 0 ); }
const int MAXN = 2e5;
const LL LINF = 1ll << 60;
int n, ecnt = 1, head[MAXN + 5], rt;
LL all, upsum, wgt[MAXN + 5];
struct Edge { int to, val, nxt; } graph[MAXN * 2 + 5];
inline void link( const int s, const int t, const int w ) {
graph[++ecnt] = { t, w, head[s] };
head[s] = ecnt;
}
namespace Subtask23 {
int siz[MAXN + 5], root;
LL sum[MAXN + 5], mx[MAXN + 5], sm[MAXN + 5], ans[2];
inline void init( const int u, const int fa ) {
siz[u] = 1, mx[u] = 0, sm[u] = -LINF;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa ) {
init( v, u );
siz[u] += siz[v], sum[u] += sum[v] + graph[i ^ 1].val;
LL d = mx[v] + graph[i].val;
if ( mx[u] < d ) sm[u] = mx[u], mx[u] = d;
else if ( sm[u] < d ) sm[u] = d;
}
}
}
inline void solve( const int u, const int fa, const LL ups, const LL upx ) {
chkmax( ans[0], sum[u] + ups );
LL tmp = sum[u] + ups + lmax( upx, mx[u] );
if ( ans[1] < tmp ) root = u, ans[1] = tmp;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa ) {
int w1 = graph[i].val, w2 = graph[i ^ 1].val;
LL ns = ups + sum[u] - sum[v] - w2 + w1;
LL nx = lmax( upx, mx[v] + w1 < mx[u] ? mx[u] : sm[u] ) + w2;
solve( v, u, ns, nx );
}
}
}
inline void main() {
init( 1, 0 );
solve( 1, 0, 0, 0 );
}
} // namespace Subtask23.
inline PIL init( const int u, const int fa ) {
PIL ret( u, 0 );
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa ) {
PIL tmp( init( v, u ) );
upsum += graph[i ^ 1].val;
wgt[tmp.first] += graph[i].val;
if ( tmp.second + graph[i].val > ret.second ) {
ret = { tmp.first, tmp.second + graph[i].val };
}
}
}
return ret;
}
int main() {
freopen( "city.in", "r", stdin );
freopen( "city.out", "w", stdout );
n = rint();
rep ( i, 2, n ) {
int u = rint(), v = rint(), a = rint(), b = rint();
all += a + b;
link( u, v, a ), link( v, u, b );
}
Subtask23::main();
rt = Subtask23::root;
init( rt, 0 );
// printf( "root is %d: ", rt );
// rep( i, 1, n ) printf( "%lld ", wgt[i] );
// puts( "" );
std::sort( wgt + 1, wgt + n + 1, []( const LL a, const LL b ) {
return a > b;
} );
rep( i, 1, n ) wgt[i] += wgt[i - 1];
for ( int q = rint(), e; q--; ) {
e = rint();
wint( all - ( e < 2 ? Subtask23::ans[0] :
upsum + wgt[e - 1] ) ), putchar( '
' );
}
return 0;
}