好几周之前学长讲了树链剖分(ps:我记得讲的时间超级短，大概不到二十分钟就讲完了~_~，那时候学长说好简单，，，，现在看起来确实不是很难）
题意：
给了一个树和各个点的权值，不超过五万个点，有以下三种操作，操作数不超过十万
I a b w ：(I是字符"I"，a，b,w是数字）表示从 a 到 b 的路径上的点的权值都加上 w
D a b w ：从 a 到 b 的路径上的点的权值都减去 w
Q a : 询问点 a 的权值是多少
这是一个树链剖分的裸题~笨宝宝wa(MLE,TLE,RE)了好多好多次~~~
呜呜呜~这篇博客非常棒~尤其是他的例子的那个图
莫名其妙的超空间
莫名其妙的超时
re是因为数组开小了~
附代码:
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std ; 8 #define LL long long 9 #define rep(i,n) for (int i = 1 ; i <= n ; ++ i) 10 11 const int maxn = 100010 ; 12 int N , R , QAQ , h[maxn] , to[maxn] , nxt[maxn] , val[maxn] , cnt , id ; 13 int dep[maxn] , siz[maxn] , son[maxn] , fa[maxn] ; 14 int top[maxn] , pos[maxn] , rk[maxn] ; 15 void Init() 16 { 17 memset(h,-1,sizeof(h)) ; 18 memset(son,-1,sizeof(son)) ; 19 cnt = id = 0 ; 20 fa[1] = 1 ; 21 } 22 23 inline void addedge(int u,int v) 24 { 25 to[cnt] = v , nxt[cnt] = h[u] , h[u] = cnt ++ ; 26 to[cnt] = u , nxt[cnt] = h[v] , h[v] = cnt ++ ; 27 } 28 void dfsa(int rt,int d) 29 { 30 dep[rt] = d , siz[rt] = 1 ; 31 int v ; 32 for (int i = h[rt] ; ~i ; i = nxt[i]) { 33 v = to[i] ; 34 if (v != fa[rt]) { 35 fa[v] = rt ; 36 dfsa(v,d+1) ; 37 siz[rt] += siz[v] ; 38 if (son[rt] == -1 || siz[v] > siz[son[rt]]) son[rt] = v ; 39 } 40 } 41 } 42 43 void dfsb(int rt,int tp) 44 { 45 pos[rt] = ++ id ; 46 top[rt] = tp ; 47 rk[pos[rt]] = rt ; 48 if (son[rt] == -1) return ; 49 dfsb(son[rt],tp) ; 50 int v ; 51 for (int i = h[rt] ; ~i ; i = nxt[i]) { 52 v = to[i] ; 53 if (v != fa[rt] && v != son[rt]) dfsb(v,v) ; 54 } 55 } 56 57 struct Node 58 { 59 int le , ri , x , tag ; 60 }A[maxn<<2]; 61 62 void Build(int i,int le,int ri) 63 { 64 A[i].le = le , A[i].ri = ri ; 65 A[i].tag = A[i].x = 0 ; 66 if (le == ri) { 67 A[i].x = val[rk[le]] ; 68 return ; 69 } 70 int mid = (le+ri)>>1 ; 71 Build(i<<1,le,mid) ; 72 Build(i<<1|1,mid+1,ri) ; 73 } 74 75 void pushDown(int i) 76 { 77 if (A[i].tag) { 78 A[i<<1].tag += A[i].tag ; 79 A[i<<1].x += A[i].tag ; 80 A[i<<1|1].tag += A[i].tag ; 81 A[i<<1|1].x += A[i].tag ; 82 A[i].tag = 0 ; 83 } 84 } 85 86 void update(int i,int le,int ri,int x) 87 { 88 if (le < A[i].le || ri > A[i].ri) return ; 89 if (A[i].le == le && A[i].ri == ri) { 90 A[i].tag += x , A[i].x += x ; 91 return ; 92 } 93 pushDown(i) ; 94 int mid = (A[i].le + A[i].ri)>>1 ; 95 if (ri <= mid) update(i<<1,le,ri,x) ; 96 else if (le > mid) update(i<<1|1,le,ri,x) ; 97 else { 98 update(i<<1,le,mid,x) ; 99 update(i<<1|1,mid+1,ri,x) ;100 }101 }102 103 int Query(int i,int p)104 {105 if (A[i].le == p && A[i].ri == p) return A[i].x ;106 pushDown(i) ;107 int mid = (A[i].le + A[i].ri)>>1 ;108 if (p <= mid) return Query(i<<1,p) ;109 else return Query(i<<1|1,p) ;110 }111 112 void solveUpdate(int u,int v,int w)113 {114 while (top[u] != top[v]) {115 if (dep[top[u]] < dep[top[v]]) swap(u,v) ;116 update(1,pos[top[u]],pos[u],w) ;117 u = fa[top[u]] ;118 }119 if (dep[u] > dep[v]) swap(u,v) ;120 update(1,pos[u],pos[v],w) ;121 }122 123 int main()124 {125 // freopen("in.txt","r",stdin) ;126 int u , v , w ;127 char c ;128 while (scanf("%d%d%d",&N,&R,&QAQ) == 3) {129 Init() ;130 rep(i,N) scanf("%d",&val[i]) ;131 rep(i,R) {132 scanf("%d%d",&u,&v) ;133 addedge(u,v) ;134 }135 dfsa(1,1) ;136 dfsb(1,1) ;137 Build(1,1,N) ;138 while (QAQ --) {139 c = getchar() ;140 while (c != 'I' && c != 'D' && c != 'Q') c = getchar() ;141 if (c == 'Q') {142 scanf("%d",&w) ;143 printf("%d\n",Query(1,pos[w])) ;144 }145 else {146 scanf("%d%d%d",&u,&v,&w) ;147 if (c == 'D') w = -w ;148 solveUpdate(u,v,w) ;149 }150 }151 }152 return 0 ;153 }
树链剖分第二发
给出的是边权
两个操作
更改第 i 条边的权值
查询 u 到 v 的路径上边权的最大值
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std ; 7 #define LL long long 8 #define rep(i,n) for (int i = 1 ; i <= n ; ++ i) 9 const int inf = 0x3f3f3f3f ; 10 const int maxn = 20010 ; 11 struct EDGE 12 { 13 int to , nxt , w ; 14 }G[maxn]; 15 struct eg 16 { 17 int u , v ; 18 }gg[maxn]; 19 int N , QAQ , h[maxn] , cnt , id , siz[maxn] , val[maxn] , son[maxn] , fa[maxn] , dep[maxn] ; 20 int top[maxn] , pos[maxn] ; 21 22 void Init() 23 { 24 rep(i,N) { 25 son[i] = h[i] = -1 ; 26 } 27 cnt = id = 0 ; 28 dep[1] = fa[1] = 0 ; 29 } 30 31 inline void addedge(int u,int v,int w,int i) 32 { 33 G[cnt] = EDGE{v,h[u],w} ; 34 h[u] = cnt ++ ; 35 G[cnt] = EDGE{u,h[v],w} ; 36 h[v] = cnt ++ ; 37 gg[i] = eg{u,v} ; 38 } 39 40 void dfsa(int rt) 41 { 42 siz[rt] = 1 ; 43 int v ; 44 for (int i = h[rt] ; ~i ; i = G[i].nxt) { 45 v = G[i].to ; 46 if (v != fa[rt]) { 47 dep[v] = dep[rt] + 1 ; 48 fa[v] = rt ; 49 dfsa(v) ; 50 siz[rt] += siz[v] ; 51 if (son[v] == -1 || siz[v] > siz[son[rt]]) son[rt] = v ; 52 } 53 } 54 } 55 56 void dfsb(int rt,int tp) 57 { 58 top[rt] = tp , pos[rt] = ++ id ; 59 if (son[rt] == -1) return ; 60 dfsb(son[rt],tp) ; 61 int v ; 62 for (int i = h[rt] ; ~i ; i = G[i].nxt) { 63 v = G[i].to ; 64 if (v == son[rt]) val[pos[v]] = G[i].w ; 65 if (v != fa[rt] && v != son[rt]) { 66 dfsb(v,v) ; 67 val[pos[v]] = G[i].w ; 68 } 69 } 70 } 71 72 struct Node 73 { 74 int le , ri , sc ; 75 }A[maxn<<2]; 76 inline int MaxMin(int a,int b) 77 { 78 return a > b ? a : b ; 79 } 80 inline void pushUp(int rt) 81 { 82 A[rt].sc = MaxMin(A[rt<<1].sc,A[rt<<1|1].sc) ; 83 } 84 void Build(int i,int le,int ri) 85 { 86 A[i] = Node{le,ri,0} ; 87 if (le == ri) { 88 A[i].sc = val[le] ; 89 return ; 90 } 91 int mid = (le + ri)/2 ; 92 Build(i<<1,le,mid) ; 93 Build(i<<1|1,mid+1,ri) ; 94 pushUp(i) ; 95 } 96 97 void update(int i,int p,int x) 98 { 99 if (A[i].le == p && A[i].ri == p) {100 A[i].sc = x ;101 return ;102 }103 int mid = (A[i].le + A[i].ri) / 2 ;104 if (p <= mid) update(i<<1,p,x) ;105 else update(i<<1|1,p,x) ;106 pushUp(i) ;107 }108 109 int Query(int i,int le,int ri)110 {111 if (A[i].le == le && A[i].ri == ri) return A[i].sc ;112 int mid = (A[i].le + A[i].ri) / 2 ;113 if (ri <= mid) return Query(i<<1,le,ri) ;114 else if (le > mid) return Query(i<<1|1,le,ri) ;115 else return MaxMin(Query(i<<1,le,mid),Query(i<<1|1,mid+1,ri)) ;116 }117 118 inline void solveQuery(int u,int v)119 {120 int ans = -inf ;121 while (top[u] != top[v]) {122 if (dep[top[u]] < dep[top[v]]) swap(u,v) ;123 ans = MaxMin(ans,Query(1,pos[top[u]],pos[u])) ;124 u = fa[top[u]] ;125 }126 if (u != v) {127 if (dep[u] > dep[v]) swap(u,v) ;128 ans = MaxMin(ans,Query(1,pos[u]+1,pos[v])) ;129 }130 printf("%d\n",ans) ;131 }132 133 inline void solveUpdate(int i,int x)134 {135 int u = gg[i].u , v = gg[i].v ;136 if (dep[u] < dep[v]) u = v ;137 update(1,pos[u],x) ;138 }139 140 int main()141 {142 // freopen("in.txt","r",stdin) ;143 int T , u , v , w ;144 char c , cc ;145 scanf("%d",&T) ;146 while (T --) {147 scanf("%d",&N) ;148 Init() ;149 rep(i,N-1) {150 scanf("%d%d%d",&u,&v,&w) ;151 addedge(u,v,w,i) ;152 }153 dfsa(1) ;154 dfsb(1,1) ;155 Build(1,1,N) ;156 while (true) {157 c = getchar() ;158 while (c != 'Q' && c != 'C' && c != 'D') c = getchar() ;159 cc = getchar() ;160 while (cc != ' ' && cc != '\n') cc = getchar() ;161 if (c == 'D') break ;162 else if (c == 'C') {163 scanf("%d%d",&u,&w) ;164 solveUpdate(u,w) ;165 }166 else {167 scanf("%d%d",&u,&v) ;168 solveQuery(u,v) ;169 }170 }171 }172 return 0 ;173 }
树链剖分模板题目
wa了一发~不开森~~~
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std ; 7 #define rep(i,n) for (int i = 1 ; i <= n ; ++ i) 8 const int maxn = 60010 ; 9 const int inf = 900000010 ; 10 struct EDGE 11 { 12 int to , nxt ; 13 }G[maxn]; 14 int N , QAQ , cnt , h[maxn] , id , val[maxn] ; 15 int son[maxn] , siz[maxn] , fa[maxn] , pos[maxn] , dep[maxn] ; 16 int top[maxn] , rk[maxn] ; 17 void Init() 18 { 19 rep(i,N) { 20 h[i] = son[i] = -1 ; 21 } 22 cnt = id = 0 ; 23 } 24 inline void addedge(int u,int v) 25 { 26 G[cnt] = EDGE{v,h[u]} ; 27 h[u] = cnt ++ ; 28 G[cnt] = EDGE{u,h[v]} ; 29 h[v] = cnt ++ ; 30 } 31 32 void dfsa(int rt,int d) 33 { 34 dep[rt] = d ; 35 siz[rt] = 1 ; 36 int v ; 37 for (int i = h[rt] ; ~i ; i = G[i].nxt) { 38 v = G[i].to ; 39 if (v != fa[rt]) { 40 fa[v] = rt ; 41 dfsa(v,d+1) ; 42 siz[rt] += siz[v] ; 43 if (son[rt] == -1 || siz[v] > siz[son[rt]]) son[rt] = v ; 44 } 45 } 46 } 47 48 void dfsb(int rt,int tp) 49 { 50 top[rt] = tp ; 51 pos[rt] = ++ id ; 52 rk[id] = rt ; 53 if (son[rt] == -1) return ; 54 dfsb(son[rt],tp) ; 55 int v ; 56 for (int i = h[rt] ; ~i ; i = G[i].nxt) { 57 v = G[i].to ; 58 if (v != fa[rt] && v != son[rt]) dfsb(v,v) ; 59 } 60 } 61 62 struct Node 63 { 64 int le , ri , x , sum ; 65 }A[maxn<<1]; 66 inline int MaxMin(int a,int b) 67 { 68 return a > b ? a : b ; 69 } 70 inline void uuuuuuuuuuuuppppppppppppp(int rt) 71 { 72 A[rt].x = MaxMin(A[rt<<1].x,A[rt<<1|1].x) ; 73 A[rt].sum = A[rt<<1].sum + A[rt<<1|1].sum ; 74 } 75 void Build(int i,int le,int ri) 76 { 77 A[i] = Node{le,ri,0,0} ; 78 if (le == ri) { 79 A[i].x = A[i].sum = val[rk[le]] ; 80 return ; 81 } 82 int mid = (le + ri) >> 1 ; 83 Build(i<<1,le,mid) ; 84 Build(i<<1|1,mid+1,ri) ; 85 uuuuuuuuuuuuppppppppppppp(i) ; 86 } 87 88 int Query(int i,int le,int ri,bool fir) 89 { 90 if (A[i].le == le && A[i].ri == ri) { 91 if (fir) return A[i].x ; 92 else return A[i].sum ; 93 } 94 int mid = (A[i].le + A[i].ri) >> 1 ; 95 if (ri <= mid) return Query(i<<1,le,ri,fir) ; 96 else if (le > mid) return Query(i<<1|1,le,ri,fir) ; 97 else { 98 int a = Query(i<<1,le,mid,fir) , b = Query(i<<1|1,mid+1,ri,fir) ; 99 if (fir) return MaxMin(a,b) ;100 else return (a + b) ;101 }102 }103 104 void update(int i,int p,int x)105 {106 if (A[i].le == p && A[i].ri == p) {107 A[i].x = A[i].sum = x ;108 return ;109 }110 int mid = (A[i].le + A[i].ri) >> 1 ;111 if (p <= mid) update(i<<1,p,x) ;112 else update(i<<1|1,p,x) ;113 uuuuuuuuuuuuppppppppppppp(i) ;114 }115 116 inline void solveQuery(int u,int v,bool fir)117 {118 int ans = -inf ;119 if (!fir) ans = 0 ;120 while (top[u] != top[v]) {121 if (dep[top[u]] < dep[top[v]]) swap(u,v) ;122 if (fir) ans = MaxMin(ans,Query(1,pos[top[u]],pos[u],fir)) ;123 else ans += Query(1,pos[top[u]],pos[u],fir) ;124 u = fa[top[u]] ;125 }126 if (dep[u] > dep[v]) swap(u,v) ;127 if (fir) ans = MaxMin(ans,Query(1,pos[u],pos[v],fir)) ;128 else ans += Query(1,pos[u],pos[v],fir) ;129 printf("%d\n",ans);130 }131 132 inline void solveUpdate(int u,int w)133 {134 update(1,pos[u],w) ;135 }136 137 int main()138 {139 // freopen("in.txt","r",stdin) ;140 int u , v , w ;141 char c , ss ;142 while (scanf("%d",&N) == 1) {143 Init() ;144 rep(i,N-1) {145 scanf("%d%d",&u,&v) ;146 addedge(u,v) ;147 }148 rep(i,N) scanf("%d",&val[i]) ;149 dfsa(1,1) ;150 dfsb(1,1) ;151 Build(1,1,N) ;152 scanf("%d",&QAQ) ;153 while (QAQ --) {154 c = getchar() ;155 while (c != 'Q' && c != 'C') c = getchar() ;156 if (c == 'Q') c = getchar() ;157 ss = getchar() ;158 while (ss != ' ') ss = getchar() ;159 scanf("%d%d",&u,&v) ;160 if (c == 'C') solveUpdate(u,v) ;161 else if (c == 'M') solveQuery(u,v,true) ;162 else solveQuery(u,v,false) ;163 }164 }165 return 0 ;166 }
树链剖分 之再来一发
先是在 vj 上wa了几发，然后在poj上wa~~~~呜呜呜呜呜~~~~~~~~~~~·
题意：
输入：给出了一棵树和边权（不超过一万个节点），若干个操作。
- CHANGE i v 把第 i 条边的权值改为 v
- NEGATE u v 把从 u 到 v 的路径上的边权置为相反数（我sb的以为是置0.。。。）
- QUERY u v 查询从 u 到 v 的路径上边权最大的权值
- DONE 操作结束
也是一个赤裸裸的树链剖分，刚开始线段树写烂了~一直wa，需要注意更新或查询u-v间路径时若在同一条链上则应从深度小的点的儿子开始
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std ; 7 #define rep(i,n) for (int i = 1 ; i <= n ; ++ i) 8 #define intmid int mid = (A[i].le + A[i].ri) >> 1 ; 9 #define lson (i<<1) 10 #define rson (i<<1|1) 11 const int maxn = 200100 ; 12 int N , cnt , id , h[maxn] , fa[maxn] , son[maxn] , siz[maxn] , dep[maxn] , top[maxn] , val[maxn] , pos[maxn] ; 13 14 struct EDGE 15 { 16 int u , to , nxt , w ; 17 }G[maxn]; 18 19 void Init() 20 { 21 memset(h,-1,sizeof(h)) ; 22 memset(son,-1,sizeof(son)) ; 23 fa[1] = cnt = id = 0 ; 24 } 25 26 inline void addedge(int u,int v,int w) 27 { 28 G[cnt] = EDGE{u,v,h[u],w} ; 29 h[u] = cnt ++ ; 30 G[cnt] = EDGE{v,u,h[v],w} ; 31 h[v] = cnt ++ ; 32 } 33 34 void dfsa(int rt,int d) 35 { 36 dep[rt] = d , siz[rt] = 1 ; 37 int v ; 38 for (int i = h[rt] ; ~i ; i = G[i].nxt) { 39 v = G[i].to ; 40 if (v != fa[rt]) { 41 fa[v] = rt ; 42 dfsa(v,d+1) ; 43 siz[rt] += siz[v] ; 44 if (son[rt] == -1 || siz[v] > siz[son[rt]]) son[rt] = v ; 45 } 46 } 47 } 48 49 void dfsb(int rt,int tp) 50 { 51 top[rt] = tp , pos[rt] = ++ id ; 52 if (son[rt] == -1) return ; 53 dfsb(son[rt],tp) ; 54 int v ; 55 for (int i = h[rt] ; ~i ; i = G[i].nxt) { 56 v = G[i].to ; 57 if (v == son[rt]) val[pos[v]] = G[i].w ; 58 if (v != son[rt] && v != fa[rt]) dfsb(v,v) ; 59 val[pos[v]] = G[i].w ; 60 } 61 } 62 63 struct segmenttree 64 { 65 int le , ri , ma , mi , tag ; 66 }A[maxn<<1]; 67 inline int Max(int a,int b) 68 { 69 return a > b ? a : b ; 70 } 71 inline int Min(int a,int b) 72 { 73 return a < b ? a : b ; 74 } 75 76 inline void pushUp(int i) 77 { 78 A[i].ma = Max(A[lson].ma,A[rson].ma) ; 79 A[i].mi = Min(A[lson].mi,A[rson].mi) ; 80 } 81 inline void ng(int i) 82 { 83 A[i].tag ++ ; 84 A[i].ma = -A[i].ma , A[i].mi = -A[i].mi ; 85 swap(A[i].ma,A[i].mi) ; 86 } 87 inline void pushDown(int i) 88 { 89 if (A[i].le == A[i].ri) return ; 90 if (A[i].tag&1) { 91 A[i].tag ++ ; 92 ng(lson) ; 93 ng(rson) ; 94 } 95 } 96 void Build(int i,int le,int ri) 97 { 98 A[i] = segmenttree{le,ri,0,0,0} ; 99 if (le == ri) {100 A[i].ma = A[i].mi = val[le] ;101 return ;102 }103 intmid ;104 Build(lson,le,mid) ;105 Build(rson,mid+1,ri) ;106 pushUp(i) ;107 }108 109 void update(int i,int p,int x)110 {111 if (A[i].le == p && A[i].ri == p) {112 A[i].ma = A[i].mi = x , A[i].tag = 0 ;113 return ;114 }115 pushDown(i) ;116 intmid ;117 if (p <= mid) update(lson,p,x) ;118 else update(rson,p,x) ;119 pushUp(i) ;120 }121 void ngupdate(int i,int le,int ri)122 {123 if (A[i].le == le && A[i].ri == ri) {124 ng(i) ;125 return ;126 }127 pushDown(i) ;128 intmid ;129 if (ri <= mid) ngupdate(lson,le,ri) ;130 else if (le > mid) ngupdate(rson,le,ri) ;131 else {132 ngupdate(lson,le,mid) ;133 ngupdate(rson,mid+1,ri) ;134 }135 pushUp(i) ;136 }137 138 int Query(int i,int le,int ri)139 {140 if (A[i].le >= le && A[i].ri <= ri) return A[i].ma ;141 intmid ;142 pushDown(i) ;143 if (ri <= mid) return Query(lson,le,ri) ;144 else if (le > mid) return Query(rson,le,ri) ;145 else return Max(Query(lson,le,mid),Query(rson,mid+1,ri)) ;146 pushUp(i) ;147 }148 149 inline void solveUpdate(int id,int w)150 {151 id = 2*id - 2 ;152 int u = G[id].u , v = G[id].to ;153 if (dep[u] < dep[v]) swap(u,v) ;154 update(1,pos[u],w) ;155 }156 157 inline void solveNgUpdate(int u,int v)158 {159 while (top[u] != top[v]) {160 if (dep[top[u]] < dep[top[v]]) swap(u,v) ;161 ngupdate(1,pos[top[u]],pos[u]) ;162 u = fa[top[u]] ;163 }164 if (u != v) {165 if (dep[u] > dep[v]) swap(u,v) ;166 ngupdate(1,pos[son[u]],pos[v]) ;167 }168 }169 170 inline void solveQuery(int u,int v)171 {172 int ans = -99999999 ;173 while (top[u] != top[v]) {174 if (dep[top[u]] < dep[top[v]]) swap(u,v) ;175 ans = Max(ans,Query(1,pos[top[u]],pos[u])) ;176 u = fa[top[u]] ;177 }178 if (u != v) {179 if (dep[u] > dep[v]) swap(u,v) ;180 ans = Max(ans,Query(1,pos[son[u]],pos[v])) ;181 }182 printf("%d\n",ans);183 }184 185 int main()186 {187 // freopen("in.txt","r",stdin) ;188 int T , u , v , w ;189 char c , ss ;190 scanf("%d",&T) ;191 while (T --) {192 scanf("%d",&N) ;193 Init() ;194 rep(i,N-1) {195 scanf("%d%d%d",&u,&v,&w) ;196 addedge(u,v,w) ;197 }198 dfsa(1,1) ;199 dfsb(1,1) ;200 Build(1,1,N) ;201 while (true) {202 c = getchar() ;203 while (c != 'C' && c != 'N' && c != 'Q' && c != 'D') c = getchar() ;204 ss = getchar() ;205 while (ss != ' ' && ss != '\n') ss = getchar() ;206 if (c == 'D') break ;207 else if (c == 'Q') {208 scanf("%d%d",&u,&v) ;209 solveQuery(u,v) ;210 }211 else if (c == 'C') {212 scanf("%d%d",&u,&v) ;213 solveUpdate(u,v) ;214 }215 else if (c == 'N') {216 scanf("%d%d",&u,&v) ;217 solveNgUpdate(u,v) ;218 }219 }220 }221 return 0 ;222 }
题意： 赤裸裸的树链剖分
思考： 此 oj 不支持 C++ 11（害我 CE 了四发）
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std ; 7 #define LL long long 8 #define rep(i,n) for (LL i = 1 ; i <= n ; ++ i) 9 #define intmid LL mid = (A[i].le + A[i].ri)>>1 ; 10 #define lson (i<<1) 11 #define rson (i<<1|1) 12 const LL maxn = 100010 ; 13 LL N , QAQ , h[maxn] , cnt , id , fa[maxn] , siz[maxn] , son[maxn] , dep[maxn] , pos[maxn] , top[maxn] ; 14 LL val[maxn] ; 15 struct EDGE 16 { 17 LL u , to , nxt ; 18 LL w ; 19 }G[maxn]; 20 21 void Init() 22 { 23 memset(son,-1,sizeof(son)) ; 24 memset(h,-1,sizeof(h)) ; 25 fa[1] = cnt = id = 0 ; 26 } 27 28 inline void addedge(LL u,LL v,LL w) 29 { 30 G[cnt].u = u , G[cnt].to = v ; 31 G[cnt].nxt = h[u] , G[cnt].w = w ; 32 h[u] = cnt ++ ; 33 G[cnt].u = v , G[cnt].to = u ; 34 G[cnt].nxt = h[v] , G[cnt].w = w ; 35 h[v] = cnt ++ ; 36 } 37 38 void dfsa(LL rt,LL d) 39 { 40 siz[rt] = 1 , dep[rt] = d ; 41 LL v ; 42 for (LL i = h[rt] ; ~i ; i = G[i].nxt) { 43 v = G[i].to ; 44 if (v != fa[rt]) { 45 fa[v] = rt ; 46 dfsa(v,d+1) ; 47 siz[rt] += siz[v] ; 48 if (son[rt] == -1 || siz[v] > siz[son[rt]]) son[rt] = v ; 49 } 50 } 51 } 52 53 void dfsb(LL rt,LL tp) 54 { 55 top[rt] = tp , pos[rt] = ++ id ; 56 if (son[rt] == -1) return ; 57 dfsb(son[rt],tp) ; 58 LL v ; 59 for (LL i = h[rt] ; ~i ; i = G[i].nxt) { 60 v = G[i].to ; 61 if (v == fa[rt]) continue ; 62 if (v != son[rt]) dfsb(v,v) ; 63 val[pos[v]] = G[i].w ; 64 } 65 } 66 67 struct segmenttree 68 { 69 LL le , ri ; 70 LL sc ; 71 }A[maxn<<1]; 72 inline void pushUp(LL i) 73 { 74 A[i].sc = A[lson].sc + A[rson].sc ; 75 } 76 void Build(LL i,LL le,LL ri) 77 { 78 A[i].le = le , A[i].ri = ri , A[i].sc = 0 ; 79 if (le == ri) { 80 A[i].sc = val[le] ; 81 return ; 82 } 83 intmid ; 84 Build(lson,le,mid) ; 85 Build(rson,mid+1,ri) ; 86 pushUp(i) ; 87 } 88 89 void update(LL i,LL p,LL x) 90 { 91 if (A[i].le == p && A[i].ri == p) { 92 A[i].sc = x ; 93 return ; 94 } 95 intmid ; 96 if (p <= mid) update(lson,p,x) ; 97 else update(rson,p,x) ; 98 pushUp(i) ; 99 }100 101 LL Query(LL i,LL le,LL ri)102 {103 if (A[i].le == le && A[i].ri == ri) return A[i].sc ;104 intmid ;105 if (ri <= mid) return Query(lson,le,ri) ;106 else if (le > mid) return Query(rson,le,ri) ;107 else return (Query(lson,le,mid) + Query(rson,mid+1,ri)) ;108 }109 110 inline void solveUpdate(LL i,LL x)111 {112 LL u = G[2*i-2].u , v = G[2*i-2].to ;113 if (dep[u] < dep[v]) swap(u,v) ;114 update(1,pos[u],x) ;115 }116 117 inline LL solveQuery(LL u,LL v)118 {119 LL ans = 0 ;120 while (top[u] != top[v]) {121 if (dep[top[u]] < dep[top[v]]) swap(u,v) ;122 ans += Query(1,pos[top[u]],pos[u]) ;123 u = fa[top[u]] ;124 }125 if (u != v) {126 if (dep[u] > dep[v]) swap(u,v) ;127 ans += Query(1,pos[son[u]],pos[v]) ;128 }129 return ans ;130 }131 132 int main()133 {134 // freopen("in.txt","r",stdin) ;135 LL u , v ;136 LL w ;137 while (scanf("%I64d%I64d",&N,&QAQ) == 2) {138 Init() ;139 rep(i,N-1) {140 scanf("%I64d%I64d%I64d",&u,&v,&w) ;141 addedge(u,v,w) ;142 }143 dfsa(1,1) ;144 dfsb(1,1) ;145 Build(1,1,N) ;146 while (QAQ --) {147 scanf("%I64d",&u) ;148 if (u == 0) {149 scanf("%I64d%I64d",&u,&w) ;150 solveUpdate(u,w) ;151 }152 else if (u == 1) {153 scanf("%I64d%I64d",&u,&v) ;154 printf("%I64d\n",solveQuery(u,v)) ;155 }156 }157 }158 return 0 ;159 }
鉴于自己的记性实在太差~~~趁现在还会一点点，还是写点什么吧~
对于裸树链剖分关键部分在于把树的所有节点映射到线段树的节点上。我习惯用两次dfs确定顺序
void dfsa(int rt,int d){ dep[rt] = d , siz[rt] = 1 ; int v ; for (int i = h[rt] ; ~i ; i = G[i].nxt) { v = G[i].to ; if (v != fa[rt]) { fa[v] = rt ; dfsa(v,d+1) ; if (son[rt] == -1 || siz[v] > siz[son[rt]]) son[rt] = v ; } }}上面的能得到树中各点的深度，重儿子，父亲节点
void dfsb(int rt,int tp){ top[rt] = tp , pos[rt] = ++ id ; if (son[rt] == -1) return ; dfsb(son[rt],tp) ; int v ; for (int i = h[rt] ; ~i ; i = G[i].nxt) { v = G[i].to ; if (v == son[rt]) val[pos[v]] = G[i].w ; if (v != son[rt] && v != fa[rt]) dfsb(v,v) ; val[pos[v]] = G[i].w ; }}
这个是为了获得各个节点在线段树中的位置（顺带把权值映射到线段树节点上），还有就是top数组了，top[i]表示与i在同一条重链上的深度最小的点，也就是最靠近树根且在同一条重链上
由这个就可以求LCA（没试过，不敢瞎说，大致就是根据top和深度（确定哪一个）不断的向上跳（刚才瞎想了一下觉得对于特定的数据会超时，比如给的数据使它每次只能跳到父节点，这样就要算他们的深度之和次了（假设不在同一条链）如果深度和很大，，，询问次数很多，，就TLE，这个是有可能的，但是要注意这需要非常非常非常非常大的N才可以，N很大的话其他的估计也不好搞）时间复杂度是log级别的，因为，在树中任意一点到根的路径上，重链数不会超过(logn),所以我们可以在O(logn)的时间复杂度内，将a，b的LCA求出来。）
然后就是更新了
1 inline void solveNgUpdate(int u,int v) 2 { 3 while (top[u] != top[v]) { 4 if (dep[top[u]] < dep[top[v]]) swap(u,v) ; 5 ngupdate(1,pos[top[u]],pos[u]) ; 6 u = fa[top[u]] ; 7 } 8 if (u != v) { 9 if (dep[u] > dep[v]) swap(u,v) ;10 ngupdate(1,pos[son[u]],pos[v]) ;11 }12 }
~end~