数N<=10^5,操作数M<=10^5,所有的颜色C为整数且在[0, 10^9]之间
题解
裸的树链剖分+线段树。
区间修改非常恶心,很多细节。
多写写应该就能好了吧。。。
#include <stdio.h> #include <algorithm> using namespace std; #define lson l , mid , x << 1 #define rson mid + 1 , r , x << 1 | 1 #define N 100005 int fa[N] , deep[N] , si[N] , val[N] , bl[N] , pos[N] , tot; int head[N] , to[N << 1] , next[N << 1] , cnt; int sum[N << 2] , lc[N << 2] , rc[N << 2] , mark[N << 2] , n; char str[10]; void add(int x , int y) { to[++cnt] = y; next[cnt] = head[x]; head[x] = cnt; } void dfs1(int x) { int i , y; si[x] = 1; for(i = head[x] ; i ; i = next[i]) { y = to[i]; if(y != fa[x]) { fa[y] = x; deep[y] = deep[x] + 1; dfs1(y); si[x] += si[y]; } } } void dfs2(int x , int c) { int k = 0 , i , y; bl[x] = c; pos[x] = ++tot; for(i = head[x] ; i ; i = next[i]) { y = to[i]; if(fa[x] != y && si[y] > si[k]) k = y; } if(k != 0) { dfs2(k , c); for(i = head[x] ; i ; i = next[i]) { y = to[i]; if(fa[x] != y && y != k) dfs2(y , y); } } } void pushup(int x) { lc[x] = lc[x << 1]; rc[x] = rc[x << 1 | 1]; sum[x] = sum[x << 1] + sum[x << 1 | 1]; if(rc[x << 1] == lc[x << 1 | 1]) sum[x] -- ; } void pushdown(int x) { int tmp = mark[x]; mark[x] = 0; if(tmp) { sum[x << 1] = sum[x << 1 | 1] = 1; lc[x << 1] = rc[x << 1] = lc[x << 1 | 1] = rc[x << 1 | 1] = tmp; mark[x << 1] = mark[x << 1 | 1] = tmp; } } void update(int b , int e , int v , int l , int r , int x) { if(b <= l && r <= e) { sum[x] = 1; lc[x] = rc[x] = v; mark[x] = v; return; } pushdown(x); int mid = (l + r) >> 1; if(b <= mid) update(b , e , v , lson); if(e > mid) update(b , e , v , rson); pushup(x); } void solveupdate(int x , int y , int v) { while(bl[x] != bl[y]) { if(deep[bl[x]] < deep[bl[y]]) { swap(x , y); } update(pos[bl[x]] , pos[x] , v , 1 , n , 1); x = fa[bl[x]]; } if(deep[x] > deep[y]) swap(x , y); update(pos[x] , pos[y] , v , 1 , n , 1); } int query(int b , int e , int l , int r , int x) { if(b <= l && r <= e) { return sum[x]; } pushdown(x); int mid = (l + r) >> 1 , ans = 0; if(b <= mid) ans += query(b , e , lson); if(e > mid) ans += query(b , e , rson); if(b <= mid && e > mid && rc[x << 1] == lc[x << 1 | 1]) ans -- ; return ans; } int getcl(int p , int l , int r , int x) { if(l == r) return lc[x]; pushdown(x); int mid = (l + r) >> 1; if(p <= mid) return getcl(p , lson); else return getcl(p , rson); } int solvequery(int x , int y) { int ans = 0; while(bl[x] != bl[y]) { if(deep[bl[x]] < deep[bl[y]]) swap(x , y); ans += query(pos[bl[x]] , pos[x] , 1 , n , 1); if(getcl(pos[bl[x]] , 1 , n , 1) == getcl(pos[fa[bl[x]]] , 1 , n , 1)) ans -- ; x = fa[bl[x]]; } if(deep[x] > deep[y]) swap(x , y); ans += query(pos[x] , pos[y] , 1 , n , 1); return ans; } int main() { int i , x , y , z , m; scanf("%d%d" , &n , &m); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &val[i]); for(i = 1 ; i < n ; i ++ ) { scanf("%d%d" , &x , &y); add(x , y); add(y , x); } dfs1(1); dfs2(1 , 1); for(i = 1 ; i <= n ; i ++ ) update(pos[i] , pos[i] , val[i] , 1 , n , 1); while(m -- ) { scanf("%s" , str); switch(str[0]) { case 'C': scanf("%d%d%d" , &x , &y , &z); solveupdate(x , y , z); break; default: scanf("%d%d" , &x , &y); printf("%d\n" , solvequery(x , y)); } } return 0; }优质内容筛选与推荐>>
1、二分查找(Binary Search)的递归和非递归
2、WebDev.WebServer40.EXE
3、.NET 中的十进制浮点类型(译文)
4、牛客练习赛14
5、window.open()打开页面