problem

luogu-P4679

理解清楚題意又是一個世紀的更迭了

給定一個樹，每個節點位置上實際放了兩個節點。

然后若干次修改和查詢。$.$ 能走，$\#$ 不能走。

詢問 $u\to v$ 的簡單路徑上最長能走的距離。（是強制從 $u$ 開始，不是問最長子段哦）

同個節點位置上放的兩個節點能否互通依舊遵循上面的規則。

solution

這種路徑問題通常我們考慮樹剖，如果涉及斷邊加邊的動態操作就考慮 $\text{LCT}$。

上樹鏈剖分的板子，兩個 $\text{dfs}$ duangduang掄上去。

然后考慮線段樹怎么維護信息能夠合并。

我們定義每個節點位置上實際存在的兩個節點分別為 $0/1$。

線段樹上每個節點維護區間 $[l,r]$ 的信息：

• $lx[2]:l$ 的 $0/1$ 節點開始能走的最長距離。

• $rx[2]:r$ 的 $0/1$ 節點開始能走的最長距離。

• $mx[2][2]:l$ 的 $0/1$ 到 $r$ 的 $0/1$ 的最長距離。

  一定是從 $l$ 的 $0/1$ 開始走，且全程不被阻擋地成功走到 $r$ 的 $0/1$ 的距離。

這有點類似線段樹維護區間最大子段和的維護方式，但略有不同。

合并兩個區間的時候，也是類似線段樹維護區間最大子段和的做法。

• $lx[i]$

  • 直接就是左兒子算的答案。$lson\to lx[i]$。

  • 左兒子整個區間走完的最大值再加上右兒子的左端點位置上的某個節點開始往后走的最大值。

    但不清楚左兒子走到其右端點位置的哪個節點更優，需要枚舉，右兒子的左端點位置同理。

    $lson\to mx[i][j]+rson\to lx[j]$。

• $rx[i]$

  • 直接右兒子算的答案。$rson\to rx[i]$。

  • 右兒子整個區間走完的最大值再加上左兒子區間右端點位置上的某個節點開始往前走的最大值。

    同理需要枚舉。

    $rson\to mx[i][j]+lson\to lx[j]$。

• $mx[i][j]$

  只能知道是從左兒子區間左端點位置的 $i$ 節點到右兒子區間右端點位置的 $j$ 節點。

  但不清楚左兒子區間右端點位置的結束節點以及右兒子區間左端點位置的開始節點，同樣需要枚舉。

  且左兒子結束節點應與右兒子開始節點一樣，不然走不過去。

  $lson\to mx[i][k]+rson\to mx[k][j]$。

合并知道了，單點修改應該就能明白。這里不再贅述。可以看下面代碼。

只說一點：因為要連續，所以如果是阻攔直接設成 $?\infty$。 這樣子就一定不可能使兩段無法到達的區間答案在線段樹上被錯誤合并。

最后需要注意一點。

我們樹剖是從上往下剖，也就是說線段樹上一個 $[l,r]$ 區間，對應的是原樹上一條從上往下的鏈的信息。

但實際上我們應該是 $u\to lca(u,v)\to v$，在樹上是先往上走再往下走。

那么往上走的信息就需要反轉區間維護的信息。

所以樹剖就不能寫代碼簡化版（通過判斷 $u,v$ 所在重鏈的深度決定是否需要交換 $u,v$）

$u,v$ 地位是不同的。

最后答案就是從 $u$ 位置的兩個節點出發能走的最遠距離的較大值，即 $ans\to lx[0/1]$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 50005 int n, m, cnt; vector < int > G[maxn]; char op[maxn][5]; int f[maxn], siz[maxn], dep[maxn], son[maxn], top[maxn], dfn[maxn], id[maxn];namespace SGT {struct node { int lx[2], rx[2], mx[2][2];node() {memset( lx, 0, sizeof( lx ) );memset( rx, 0, sizeof( rx ) );memset( mx, 0, sizeof( mx ) );} }t[maxn << 2];#define lson now << 1#define rson now << 1 | 1#define mid (l + r >> 1)node operator + ( node ls, node rs ) {node ans;memset( ans.mx, -0x3f, sizeof( ans.mx ) );for( int i = 0;i <= 1;i ++ )for( int j = 0;j <= 1;j ++ ) {ans.lx[i] = max( ans.lx[i], max( ls.lx[i], ls.mx[i][j] + rs.lx[j] ) );ans.rx[i] = max( ans.rx[i], max( rs.rx[i], rs.mx[j][i] + ls.rx[j] ) );for( int k = 0;k <= 1;k ++ )ans.mx[i][j] = max( ans.mx[i][j], ls.mx[i][k] + rs.mx[k][j] );}return ans;}node init( char *op ) {node ans;if( op[0] == '.' and op[1] == '.' ) {ans.lx[0] = ans.lx[1] = ans.rx[0] = ans.rx[1] = 2;ans.mx[0][0] = ans.mx[1][1] = 1;ans.mx[0][1] = ans.mx[1][0] = 2;}else if( op[0] == '.' or op[1] == '.' ) {int d = op[1] == '.';memset( ans.mx, -0x3f, sizeof( ans.mx ) );ans.lx[d] = ans.rx[d] = ans.mx[d][d] = 1;ans.lx[!d] = ans.rx[!d] = 0; }else {ans.lx[0] = ans.lx[1] = ans.rx[0] = ans.rx[1] = 0;memset( ans.mx, -0x3f, sizeof( ans.mx ) );}return ans;}void reverse( node &ans ) {swap( ans.lx[0], ans.rx[0] );swap( ans.lx[1], ans.rx[1] );swap( ans.mx[0][1], ans.mx[1][0] );}void modify( int now, int l, int r, int p ) {if( l == r ) { t[now] = init( op[id[l]] ); return; }if( p <= mid ) modify( lson, l, mid, p );else modify( rson, mid + 1, r, p );t[now] = t[lson] + t[rson];}node query( int now, int l, int r, int L, int R ) {if( L <= l and r <= R ) return t[now];if( R <= mid ) return query( lson, l, mid, L, R );else if( mid < L ) return query( rson, mid + 1, r, L, R );else return query( lson, l, mid, L, R ) + query( rson, mid + 1, r, L, R );} }namespace Qtree {void dfs1( int u, int fa ) {f[u] = fa, siz[u] = 1, dep[u] = dep[fa] + 1;for( int v : G[u] ) {if( v == fa ) continue;else dfs1( v, u );siz[u] += siz[v];if( siz[v] > siz[son[u]] ) son[u] = v;}}void dfs2( int u, int t ) {id[dfn[u] = ++ cnt] = u, top[u] = t;if( son[u] ) dfs2( son[u], t );else return;for( int v : G[u] ) if( v ^ f[u] and v ^ son[u] ) dfs2( v, v );}int query( int x, int y ) {SGT :: node ans1, ans2, ans;while( top[x] ^ top[y] ) {if( dep[top[x]] > dep[top[y]] )ans1 = SGT :: query( 1, 1, n, dfn[top[x]], dfn[x] ) + ans1, x = f[top[x]];elseans2 = SGT :: query( 1, 1, n, dfn[top[y]], dfn[y] ) + ans2, y = f[top[y]];}if( dep[x] > dep[y] ) ans1 = SGT :: query( 1, 1, n, dfn[y], dfn[x] ) + ans1;else ans2 = SGT :: query( 1, 1, n, dfn[x], dfn[y] ) + ans2;reverse( ans1 );ans = ans1 + ans2;return max( ans.lx[0], ans.lx[1] );} }int main() {scanf( "%d %d", &n, &m );for( int i = 1, u, v;i < n;i ++ ) {scanf( "%d %d", &u, &v );G[u].push_back( v );G[v].push_back( u );}Qtree :: dfs1( 1, 0 );Qtree :: dfs2( 1, 1 );for( int i = 1;i <= n;i ++ ) {scanf( "%s", op[i] );SGT :: modify( 1, 1, n, dfn[i] );}char opt[5]; int u, v;while( m -- ) {scanf( "%s", opt );if( opt[0] == 'C' ) {scanf( "%d", &u );scanf( "%s", op[u] );SGT :: modify( 1, 1, n, dfn[u] );}else {scanf( "%d %d", &u, &v );printf( "%d\n", Qtree :: query( u, v ) );}}return 0; }

總結

以上是生活随笔為你收集整理的[ZJOI2011] 道馆之战（树链剖分）的全部內容，希望文章能夠幫你解決所遇到的問題。

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