\(\mathcal{Description}\)
Link.
给定一棵含 \(n\) 个结点的树,双向边权不相同。\(q\) 次询问,每次询问在树上标记 \(e\) 个点,标记的价值为所有趋向于某个标记点的有向边权值之和,求价值的最大值。
\(q\le n\le2\times10^5\)。
\(\mathcal{Solution}\)
\(e=1\text{ or }2\) 的时候可以直接换根求解。需要强调的是,当确定一个被标记的根时,其余标记点的贡献为根到这个标记点的有向路径长度(取并)。接下来引入一些结论。首先有:
对于一棵根被钦定标记的树(\(e=1\)),当 \(e=k<n\) 时,一定能通过标记深度最深的结点使得其成为 \(e=k\) 时的最优解。
不难意会。(
由此可以推出一个关键的结论:
对于 \(k>2\),\(e=k\) 时的最优解必然通过在某个 \(e=k-1\) 时的最优解的基础上新标记一个点得到。
记 \(e=k\) 时某个最优解标记点集合为 \(S\),\(e=k+1\) 时任一最优解的标记点集合为 \(T\),考虑反证,若不存在 \(S\sub T\):
- 若 \(S\cap T\neq\varnothing\),取一个 \(r\in S\cap T\),标记并作为树根。由上一个结论,矛盾。
- 若 \(S\cap T=\varnothing\),考虑把 \(T\) 中的一个结点丢到 \(S\) 中,此时 \(S\) 不会比 \(T\) 劣。
所以,以 \(e=2\) 时的一个标记点为根,令每片叶子的权值为其保持作为子树最深点,向上能爬的距离。排序取前 \(k\) 大之和加上一些常数就是 \(e=k\) 的答案。复杂度 \(\mathcal O(n\log 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( '\n' );
}
return 0;
}