problem
luogu-P3345
solution
这是一个带权重心的题，考察动态点分治。点分治？呵，不可能的，这辈子都不可能写点分治
我们重新考虑重心的性质：以这个点为根时，所有子树的大小不会超过整体大小的一半。
带权重心无非是树上每个点不再是等权的
1
1
1，而是
d
i
d_i
di?。
考虑随机从一个点走向重心：当前假设重心为
x
x
x，我们维护一个值
s
i
z
x
siz_x
sizx? 表示
x
x
x 所在子树所有节点的权值和。
那么如果存在一个
x
x
x 的子节点
y
y
y，满足
2
?
s
i
z
y
>
2*siz_y>
2?sizy?>
x
x
x 树中所有点的权值和，则
y
y
y 更优，否则
x
x
x 更优。
比较暴力的想法就是从根节点一路往下找，但这样每次
O
(
n
)
O(n)
O(n) 搜一遍树时间开销过大，这是因为走了很多没有用的点。
因此我们考虑树链剖分，这样可以获得一个
dfs
\text{dfs}
dfs 序，然后用线段树维护区间
s
i
z
siz
siz 的最大值。
树链剖分得到的
dfs
\text{dfs}
dfs 序中深度深的节点
dfs
\text{dfs}
dfs 序更大。
查询时就在线段树上二分，每次分为
[
l
,
m
i
d
]
,
(
m
i
d
,
r
]
[l,mid],(mid,r]
[l,mid],(mid,r]，只要
(
m
i
d
,
r
]
(mid,r]
(mid,r] 区间的最大值满足重心判断就往右子树走，否则走左子树。
时间复杂度
O
(
log
?
n
)
O(\log n)
O(logn)。
现在假设已经求出了重心
x
x
x，接下来考虑如何计算答案。
a
n
s
=
∑
i
d
i
?
d
i
s
(
x
,
i
)
=
∑
i
d
i
?
(
d
e
p
x
+
d
e
p
i
?
2
?
d
e
p
l
c
a
(
x
,
i
)
)
=
d
e
p
x
∑
d
i
+
∑
d
i
?
d
e
p
i
?
2
∑
d
i
?
d
e
p
l
c
a
(
x
,
i
)
ans=\sum_id_i*dis(x,i)=\sum_id_i*(dep_x+dep_i-2*dep_{lca(x,i)}) \\=dep_x\sum d_i+\sum d_i*dep_i-2\sum d_i*dep_{lca(x,i)}
ans=i∑?di??dis(x,i)=i∑?di??(depx?+depi??2?deplca(x,i)?)=depx?∑di?+∑di??depi??2∑di??deplca(x,i)?
∑
d
i
,
∑
d
i
?
d
e
p
i
\sum d_i,\sum d_i*dep_i
∑di?,∑di??depi? 直接用两个变量维护即可，问题在于如何维护
∑
d
i
?
d
e
p
l
c
a
(
x
,
i
)
\sum d_i*dep_{lca(x,i)}
∑di??deplca(x,i)?。
其实这是一个很经典的树链剖分维护形式。
当
d
i
←
+
w
d_i\leftarrow +w
di?←+w 时，把
i
i
i 到根路径上所有点均
+
w
+w
+w，然后查询
x
x
x 到根路径上的点权值和。
先树差分一下，即在线段树中
i
i
i 存储
d
e
p
i
?
d
e
p
f
a
i
dep_i-dep_{fa_i}
depi??depfai??。这样从
i
i
i 一路加到根上面算出的才是
i
i
i 这个点本身的实际贡献。
很好写，时间复杂度
O
(
n
log
?
2
n
)
O(n\log ^2n)
O(nlog2n) 也能跑过。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100005
int n, Q;
vector < pair < int, int > > G[maxn];
int f[maxn], dep[maxn], dfn[maxn], id[maxn];
namespace SGT {
struct node { int Max, sum, val, tag; }t[maxn << 2];
#define lson now << 1
#define rson now << 1 | 1
#define mid (l + r >> 1)
void build( int now, int l, int r ) {
if( l == r ) { t[now].val = dep[id[l]] - dep[f[id[l]]]; return; }
build( lson, l, mid );
build( rson, mid + 1, r );
t[now].val = t[lson].val + t[rson].val;
}
void pushdown( int now ) {
if( ! t[now].tag ) return;
t[lson].tag += t[now].tag;
t[lson].Max += t[now].tag;
t[lson].sum += t[lson].val * t[now].tag;
t[rson].tag += t[now].tag;
t[rson].Max += t[now].tag;
t[rson].sum += t[rson].val * t[now].tag;
t[now].tag = 0;
}
void modify( int now, int l, int r, int L, int R, int x ) {
if( R < l or r < L ) return;
if( L <= l and r <= R ) {
t[now].tag += x;
t[now].Max += x;
t[now].sum += t[now].val * x;
return;
}
pushdown( now );
modify( lson, l, mid, L, R, x );
modify( rson, mid + 1, r, L, R, x );
t[now].Max = max( t[lson].Max, t[rson].Max );
t[now].sum = t[lson].sum + t[rson].sum;
}
int query( int now, int l, int r, int L, int R ) {
if( R < l or r < L ) return 0;
if( L <= l and r <= R ) return t[now].sum;
pushdown( now );
return query( lson, l, mid, L, R ) + query( rson, mid + 1, r, L, R );
}
int query( int x ) {
int now = 1, l = 1, r = n;
while( l ^ r ) {
pushdown( now );
if( t[rson].Max >= x ) now = rson, l = mid + 1;
else now = lson, r = mid;
}
return id[l];
}
}
namespace Qtree {
int cnt = 0;
int son[maxn], siz[maxn], top[maxn];
void dfs1( int u, int fa ) {
f[u] = fa; siz[u] = 1;
for( int i = 0;i < G[u].size();i ++ ) {
int v = G[u][i].first, w = G[u][i].second;
if( v == fa ) continue;
else dep[v] = dep[u] + w, dfs1( v, u );
siz[u] += siz[v];
if( siz[v] > siz[son[u]] ) son[u] = v;
}
}
void dfs2( int u, int t ) {
top[u] = t, id[dfn[u] = ++ cnt] = u;
if( son[u] ) dfs2( son[u], t );
else return;
for( int i = 0;i < G[u].size();i ++ ) {
int v = G[u][i].first;
if( v == f[u] or v == son[u] ) continue;
else dfs2( v, v );
}
}
void modify( int x, int y ) {
while( top[x] ) {
SGT :: modify( 1, 1, n, dfn[top[x]], dfn[x], y );
x = f[top[x]];
}
}
int query( int x ) {
int ans = 0;
while( top[x] ) {
ans += SGT :: query( 1, 1, n, dfn[top[x]], dfn[x] );
x = f[top[x]];
}
return ans;
}
}
signed main() {
scanf( "%lld %lld", &n, &Q );
for( int i = 1, u, v, w;i < n;i ++ ) {
scanf( "%lld %lld %lld", &u, &v, &w );
G[u].push_back( make_pair( v, w ) );
G[v].push_back( make_pair( u, w ) );
}
Qtree :: dfs1( 1, 0 );
Qtree :: dfs2( 1, 1 );
SGT :: build( 1, 1, n );
int x, y, sum1 = 0, sum2 = 0;
while( Q -- ) {
scanf( "%lld %lld", &x, &y );
Qtree :: modify( x, y );
sum1 += dep[x] * y;
sum2 += y;
int p = SGT :: query( sum2 + 1 >> 1 );
printf( "%lld\n", sum1 + dep[p] * sum2 - (Qtree :: query( p ) << 1) );
}
return 0;
}
|