cms网站代理,网站类网站开发源代码,社交(sns)网站的完整设计思路,丹麦网站后缀problem
luogu-P4679
理解清楚题意又是一个世纪的更迭了
给定一个树#xff0c;每个节点位置上实际放了两个节点。
然后若干次修改和查询。... 能走#xff0c;#\## 不能走。
询问 u→vu\rightarrow vu→v 的简单路径上最长能走的距离。#xff08;是强制从 uuu 开始每个节点位置上实际放了两个节点。
然后若干次修改和查询。... 能走#\## 不能走。
询问 u→vu\rightarrow vu→v 的简单路径上最长能走的距离。是强制从 uuu 开始不是问最长子段哦
同个节点位置上放的两个节点能否互通依旧遵循上面的规则。
solution
这种路径问题通常我们考虑树剖如果涉及断边加边的动态操作就考虑 LCT\text{LCT}LCT。
上树链剖分的板子两个 dfs\text{dfs}dfs duangduang抡上去。
然后考虑线段树怎么维护信息能够合并。
我们定义每个节点位置上实际存在的两个节点分别为 0/10/10/1。
线段树上每个节点维护区间 [l,r][l,r][l,r] 的信息 lx[2]:llx[2]:llx[2]:l 的 0/10/10/1 节点开始能走的最长距离。 rx[2]:rrx[2]:rrx[2]:r 的 0/10/10/1 节点开始能走的最长距离。 mx[2][2]:lmx[2][2]:lmx[2][2]:l 的 0/10/10/1 到 rrr 的 0/10/10/1 的最长距离。 一定是从 lll 的 0/10/10/1 开始走且全程不被阻挡地成功走到 rrr 的 0/10/10/1 的距离。
这有点类似线段树维护区间最大子段和的维护方式但略有不同。
合并两个区间的时候也是类似线段树维护区间最大子段和的做法。 lx[i]lx[i]lx[i] 直接就是左儿子算的答案。lson→lx[i]lson\rightarrow lx[i]lson→lx[i]。 左儿子整个区间走完的最大值再加上右儿子的左端点位置上的某个节点开始往后走的最大值。 但不清楚左儿子走到其右端点位置的哪个节点更优需要枚举右儿子的左端点位置同理。 lson→mx[i][j]rson→lx[j]lson\rightarrow mx[i][j]rson\rightarrow lx[j]lson→mx[i][j]rson→lx[j]。 rx[i]rx[i]rx[i] 直接右儿子算的答案。rson→rx[i]rson\rightarrow rx[i]rson→rx[i]。 右儿子整个区间走完的最大值再加上左儿子区间右端点位置上的某个节点开始往前走的最大值。 同理需要枚举。 rson→mx[i][j]lson→lx[j]rson\rightarrow mx[i][j]lson\rightarrow lx[j]rson→mx[i][j]lson→lx[j]。 mx[i][j]mx[i][j]mx[i][j] 只能知道是从左儿子区间左端点位置的 iii 节点到右儿子区间右端点位置的 jjj 节点。 但不清楚左儿子区间右端点位置的结束节点以及右儿子区间左端点位置的开始节点同样需要枚举。 且左儿子结束节点应与右儿子开始节点一样不然走不过去。 lson→mx[i][k]rson→mx[k][j]lson\rightarrow mx[i][k]rson\rightarrow mx[k][j]lson→mx[i][k]rson→mx[k][j]。
合并知道了单点修改应该就能明白。这里不再赘述。可以看下面代码。
只说一点因为要连续所以如果是阻拦直接设成 −∞-\infty−∞。 这样子就一定不可能使两段无法到达的区间答案在线段树上被错误合并。
最后需要注意一点。
我们树剖是从上往下剖也就是说线段树上一个 [l,r][l,r][l,r] 区间对应的是原树上一条从上往下的链的信息。
但实际上我们应该是 u→lca(u,v)→vu\rightarrow lca(u,v)\rightarrow vu→lca(u,v)→v在树上是先往上走再往下走。
那么往上走的信息就需要反转区间维护的信息。
所以树剖就不能写代码简化版通过判断 u,vu,vu,v 所在重链的深度决定是否需要交换 u,vu,vu,v
u,vu,vu,v 地位是不同的。
最后答案就是从 uuu 位置的两个节点出发能走的最远距离的较大值即 ans→lx[0/1]ans\rightarrow lx[0/1]ans→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;
}
