大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
做题情绪:这题思路好想。调试代码调试了好久。第一次写线段树区间合并。
解题思路:
树链剖分 + 线段树区间合并
线段树的端点记录左右区间的颜色。颜色数目。合并的时候就用区间合并的思想。
还要注意一点。在由一条链转到还有一条链的时候要推断当前节点是否与父亲节点是否同一种颜色。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<cctype> #include<iomanip> #include<algorithm> using namespace std ; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const int mod = 1e9 + 7 ; const int MY = 1400 + 5 ; const int MX = 100000 + 5 ; int n ,m ,idx ,num ; int head[MX] ,ti[MX] ,top[MX] ,dep[MX] ,siz[MX] ,son[MX] ,father[MX] ,g[MX] ; struct Edge { int v ,next ; }E[MX*2] ; void addedge(int u ,int v) { E[num].v = v ; E[num].next = head[u] ; head[u] = num++ ; E[num].v = u ; E[num].next = head[v] ; head[v] = num++ ; } void dfs_find(int u ,int fa) { dep[u] = dep[fa] + 1 ; siz[u] = 1 ; son[u] = 0 ; father[u] = fa ; for(int i = head[u] ;i != -1 ;i = E[i].next) { int v = E[i].v ; if(v == fa) continue ; dfs_find(v ,u) ; siz[u] += siz[v] ; if(siz[son[u]] < siz[v]) son[u] = v ; } } void dfs_time(int u ,int fa) { ti[u] = idx++ ; top[u] = fa ; if(son[u]) dfs_time(son[u] ,top[u]) ; for(int i = head[u] ;i != -1 ;i = E[i].next) { int v = E[i].v ; if(v == father[u] || v == son[u]) continue ; dfs_time(v ,v) ; } } struct node { int le ,rt ,lc ,rc ,num ,add ; }T[MX*4] ; void build(int x ,int le ,int rt) { T[x].le = le ; T[x].rt = rt ; T[x].lc = T[x].rc = T[x].add = -1 ; T[x].num = 0 ; if(le == rt) return ; int Mid = (le + rt)>>1 ; build(L(x) ,le ,Mid) ; build(R(x) ,Mid + 1 ,rt) ; } void push_down(int x) { if(T[x].add != -1) { // 左 T[L(x)].lc = T[L(x)].rc = T[L(x)].add = T[x].add ; T[L(x)].num = 1 ; // 右 T[R(x)].lc = T[R(x)].rc = T[R(x)].add = T[x].add ; T[R(x)].num = 1 ; T[x].add = -1 ; } } void push_up(int x) { T[x].num = T[L(x)].num + T[R(x)].num ; if(T[L(x)].rc == T[R(x)].lc) T[x].num -- ; T[x].lc = T[L(x)].lc ; T[x].rc = T[R(x)].rc ; } void update(int x ,int le ,int rt ,int w) // 更新某个区间 { if(T[x].le == le && T[x].rt == rt) { T[x].add = w ; T[x].lc = w ; T[x].rc = w ; T[x].num = 1 ; return ; } push_down(x) ; int Mid = (T[x].le + T[x].rt)>>1 ; if(le > Mid) update(R(x) ,le ,rt ,w) ; else if(rt <= Mid) update(L(x) ,le ,rt ,w) ; else { update(L(x) ,le ,Mid ,w) ; update(R(x) ,Mid+1 ,rt ,w) ; } push_up(x) ; } int Query(int x ,int le ,int rt) { if(T[x].le == le && T[x].rt == rt) return T[x].num ; int Mid = (T[x].le + T[x].rt)>>1 ; push_down(x) ; if(le > Mid) return Query(R(x) ,le ,rt) ; else if(rt <= Mid) return Query(L(x) ,le ,rt) ; else { int mx = 0 ; if(T[L(x)].rc == T[R(x)].lc) mx = -1 ; return Query(L(x) ,le ,Mid) + Query(R(x) ,Mid+1 ,rt) + mx ; } push_up(x) ; } int Querynode(int x ,int pos) { if(T[x].le == T[x].rt) return T[x].lc ; int Mid = (T[x].le + T[x].rt)>>1 ; push_down(x) ; if(pos <= Mid) return Querynode(L(x) ,pos) ; else return Querynode(R(x) ,pos) ; push_up(x) ; } void LCAC(int u ,int v ,int w) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u ,v) ; update(1 ,ti[top[u]] ,ti[u] ,w) ; u = father[top[u]] ; } if(dep[u] > dep[v]) swap(u ,v) ; update(1 ,ti[u] ,ti[v] ,w) ; } int LCAQ(int u ,int v) { int ans = 0 ; while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u ,v) ; ans += Query(1 ,ti[top[u]] ,ti[u]) ; if(Querynode(1 ,ti[top[u]]) == Querynode(1 ,ti[father[top[u]]])) ans-- ; u = father[top[u]] ; } if(dep[u] > dep[v]) swap(u ,v) ; ans += Query(1 ,ti[u] ,ti[v]) ; return ans ; } int main() { while(~scanf("%d%d" ,&n ,&m)) { int u ,v ,w ; num = 0 ; memset(head ,-1 ,sizeof(head)) ; for(int i = 1 ;i <= n ; ++i) scanf("%d" ,&g[i]) ; for(int i = 1 ;i < n ; ++i) { scanf("%d%d" ,&u ,&v) ; addedge(u ,v) ; } dep[1] = siz[0] = 0 ; dfs_find(1 ,1) ; idx = 1 ; dfs_time(1 ,1) ; build(1 ,1 ,n) ; for(int i = 1 ;i <= n ; ++i) update(1 ,ti[i] ,ti[i] ,g[i]) ; char s[5] ; for(int i = 0 ;i < m ; ++i) { scanf("%s" ,s) ; scanf("%d%d" ,&u ,&v) ; if(s[0] == 'C') { scanf("%d" ,&w) ; LCAC(u ,v ,w) ; } else if(s[0] == 'Q') printf("%d\n" ,LCAQ(u ,v)) ; } } return 0 ; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117566.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...