problem

luogu-P3345

solution

這是一個帶權重心的題，考察動態點分治。點分治？呵，不可能的，這輩子都不可能寫點分治

我們重新考慮重心的性質：以這個點為根時，所有子樹的大小不會超過整體大小的一半。

帶權重心無非是樹上每個點不再是等權的 $1$，而是 $d_i$。

考慮隨機從一個點走向重心：當前假設重心為 $x$，我們維護一個值 $si{z}_x$ 表示 $x$ 所在子樹所有節點的權值和。

那么如果存在一個 $x$ 的子節點 $y$，滿足 $2?si{z}_y>$ $x$ 樹中所有點的權值和，則 $y$ 更優，否則 $x$ 更優。

比較暴力的想法就是從根節點一路往下找，但這樣每次 $O(n)$ 搜一遍樹時間開銷過大，這是因為走了很多沒有用的點。

因此我們考慮樹鏈剖分，這樣可以獲得一個 $\text{dfs}$ 序，然后用線段樹維護區間 $siz$ 的最大值。

樹鏈剖分得到的 $\text{dfs}$ 序中深度深的節點 $\text{dfs}$ 序更大。

查詢時就在線段樹上二分，每次分為 $[l,mid],(mid,r]$，只要 $(mid,r]$ 區間的最大值滿足重心判斷就往右子樹走，否則走左子樹。

時間復雜度 $O(\log n)$。

---

現在假設已經求出了重心 $x$，接下來考慮如何計算答案。
$$\begin{gathered} ans=\sum _i{d}_i?dis(x,i)=\sum _i{d}_i?(de{p}_x+de{p}_i?2?de{p}_{lca(x,i)}) \\ =de{p}_x\sum d_i+\sum d_i?de{p}_i?2\sum d_i?de{p}_{lca(x,i)} \end{gathered}$$
$\sum d_i,\sum d_i?de{p}_i$ 直接用兩個變量維護即可，問題在于如何維護 $\sum d_i?de{p}_{lca(x,i)}$。

其實這是一個很經典的樹鏈剖分維護形式。

當 $d_i\leftarrow +w$ 時，把 $i$ 到根路徑上所有點均 $+w$，然后查詢 $x$ 到根路徑上的點權值和。

先樹差分一下，即在線段樹中 $i$ 存儲 $de{p}_i?de{p}_{f{a}_i}$。這樣從 $i$ 一路加到根上面算出的才是 $i$ 這個點本身的實際貢獻。

很好寫，時間復雜度 $O(n{\log }^{2}n)$ 也能跑過。

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; }

總結

以上是生活随笔為你收集整理的[ZJOI2015] 幻想乡战略游戏（树链剖分 + 线段树二分 + 带权重心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。