[SDOI2011]染色
简化题意 (:)
给定一棵点带权的树,维护两种操作 (:)
1.把 ((x,y)) 这条链上的点权全部置为 (w).
2.查询 ((x,y)) 这条链上有多少不同的点权.
树剖 (+) 线段树维护即可.
线段树维护覆盖标记,权值个数和左端点右端点的权值.
向上合并的时候判断,左儿子的右端点权值和右儿子的左端点权值是否相同,如果相同就 (-1) .
查询的时候,合并左右儿子查询上来的信息时也要类似处理.
这样线段树的问题就解决了.
那么做完了嘛 (?)
没有,你发现树剖跳链的时候也会有合并问题.
那怎么办呢 (?) 由于树剖跳链是两边跳,所以你需要分别维护每一边的最后一个权值是什么,再下一次跳链的时候判断是否和上一次重复即可.(充分利用树剖 (+) 线段树的结构性质).
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 1e6 + 100 ;
vector < int > G[N] ;
int n , m , v[N] , siz[N] , idx[N] , w[N] ;
int deep[N] , son[N] , top[N] , f[N] , cnt ;
int L , R , color_l , color_r ;
class Tree {
#define mid ( ( l + r ) >> 1ll )
private : struct seg { int ls , rs , data , lc , rc , tag ; } t[N<<1] ;
private : int num ;
public :
inline void clear () { num = 1 ; return ; }
private :
inline void pushup (int rt) {
t[rt].lc = t[t[rt].ls].lc ; t[rt].rc = t[t[rt].rs].rc ;
t[rt].data = t[t[rt].ls].data + t[t[rt].rs].data ;
if ( t[t[rt].ls].rc == t[t[rt].rs].lc ) -- t[rt].data ;
return ;
}
public :
inline void build (int rt , int l , int r) {
t[rt].tag = 0 ;
if ( l == r ) { t[rt].data = 1ll ; t[rt].lc = t[rt].rc = w[l] ; return ; }
t[rt].ls = ++ num ; build ( t[rt].ls , l , mid ) ;
t[rt].rs = ++ num ; build ( t[rt].rs , mid + 1 , r ) ;
pushup ( rt ) ; return ;
}
private :
inline void pushdown (int rt) {
t[t[rt].ls].tag = t[t[rt].rs].tag = t[rt].tag ;
t[t[rt].ls].data = t[t[rt].rs].data = 1ll ;
t[t[rt].ls].lc = t[t[rt].ls].rc = t[rt].tag ;
t[t[rt].rs].lc = t[t[rt].rs].rc = t[rt].tag ;
t[rt].tag = 0 ; return ;
}
public :
inline void cover (int rt , int l , int r , int ll , int rr , int key) {
if ( l == ll && r == rr ) {
t[rt].data = 1ll ; t[rt].tag = key ;
t[rt].lc = t[rt].rc = key ; return ;
}
if ( t[rt].tag ) pushdown ( rt ) ;
if ( rr <= mid ) cover ( t[rt].ls , l , mid , ll , rr , key ) ;
else if ( ll > mid ) cover ( t[rt].rs , mid + 1 , r , ll , rr , key ) ;
else cover ( t[rt].ls , l , mid , ll , mid , key ) , cover ( t[rt].rs , mid + 1 , r , mid + 1 , rr , key ) ;
pushup ( rt ) ; return ;
}
public :
inline int query (int rt , int l , int r , int ll , int rr) {
if ( l == L ) color_l = t[rt].lc ;
if ( r == R ) color_r = t[rt].rc ;
if ( l == ll && r == rr ) return t[rt].data ;
if ( t[rt].tag ) pushdown ( rt ) ;
if ( rr <= mid ) return query ( t[rt].ls , l , mid , ll , rr ) ;
else if ( ll > mid ) return query ( t[rt].rs , mid + 1 , r , ll , rr ) ;
else {
int res = query ( t[rt].ls , l , mid , ll , mid ) + query ( t[rt].rs , mid + 1 , r , mid + 1 , rr ) ;
if ( t[t[rt].ls].rc == t[t[rt].rs].lc ) -- res ; return res ;
}
}
#undef mid
} T ;
inline void dfs (int cur , int anc , int dep) {
siz[cur] = 1 ; f[cur] = anc ; deep[cur] = dep ;
int maxson = - 1 ; for (int k : G[cur]) {
if ( k == anc ) continue ;
dfs ( k , cur , dep + 1 ) ; siz[cur] += siz[k] ;
if ( siz[k] > maxson ) maxson = siz[k] , son[cur] = k ;
}
return ;
}
inline void _dfs (int cur , int topf) {
top[cur] = topf ; idx[cur] = ++ cnt ; w[cnt] = v[cur] ;
if ( ! son[cur] ) return ; _dfs ( son[cur] , topf ) ;
for (int k : G[cur] ) {
if ( k == f[cur] || k == son[cur] ) continue ;
_dfs ( k , k ) ;
}
return ;
}
inline void uprange (int x , int y , int key) {
while ( top[x] != top[y] ) {
if ( deep[top[x]] < deep[top[y]] ) swap ( x , y ) ;
T.cover ( 1 , 1 , cnt , idx[top[x]] , idx[x] , key ) ;
x = f[top[x]] ;
}
if ( deep[x] > deep[y] ) swap ( x , y ) ;
T.cover ( 1 , 1 , cnt , idx[x] , idx[y] , key ) ;
return ;
}
inline int qrange (int x , int y) {
int res = 0 , lastx = - 1 , lasty = - 1 ;
while ( top[x] != top[y] ) {
if ( deep[top[x]] < deep[top[y]] )
swap ( x , y ) , swap ( lastx , lasty ) ;
L = idx[top[x]] ; R = idx[x] ;
res += T.query ( 1 , 1 , cnt , idx[top[x]] , idx[x] ) ;
if ( color_r == lastx ) -- res ; lastx = color_l ;
x = f[top[x]] ;
}
if ( deep[x] > deep[y] ) swap ( x , y ) , swap ( lastx , lasty ) ;
L = idx[x] ; R = idx[y] ;
res += T.query ( 1 , 1 , cnt , idx[x] , idx[y] ) ;
if ( color_l == lastx ) -- res ;
if ( color_r == lasty ) -- res ;
return res ;
}
signed main (int argc , char * argv[]) {
n = rint () ; m = rint () ;
rep ( i , 1 , n ) v[i] = rint () ;
rep ( i , 2 , n ) {
int u = rint () , v = rint () ;
G[u].pb ( v ) ; G[v].pb ( u ) ;
}
dfs ( 1 , 0 , 1 ) ; _dfs ( 1 , 1 ) ;
T.clear () ; T.build ( 1 , 1 , cnt ) ;
char opt[3] ;
while ( m -- ) {
scanf ("%s" , opt ) ;
int x = rint () , y = rint () ;
if ( opt[0] == 'C' ) {
int z = rint () ;
uprange ( x , y , z ) ;
} else printf ("%lld
" , qrange ( x , y ) ) ;
}
#ifndef ONLINE_JUDGE
system ("pause") ;
#endif
return 0 ;
}