樹鏈剖分模版題。

#include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cctype> #include <cmath> #define rep(i, l, r) for(int i=l; i<=r; i++) #define clr(x, c) memset(x, c, sizeof(x)) #define travel(x) for(edge *p=fir[x]; p; p=p->n) #define k(x) Key[x] #define t(x) Tree[x] #define s(x) Size[x] #define b(x) Belong[x] #define low(x) Lower[x] #define dep(x) Deep[x] #define h(x) Head[x] #define l(x) Left[x] #define r(x) Right[x] #define w(x) Where[x] #define maxn 30009 #define maxp 5000009 #define inf 0x7fffffff using namespace std; inline int read() {int x=0, f=1; char ch=getchar();while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while (isdigit(ch)) x=x*10+ch-'0', ch=getchar();return x*f; } struct edge{int y; edge *n;} e[maxn*2], *fir[maxn], *pt=e; inline void AddE(int x, int y) {pt->y=y, pt->n=fir[x], fir[x]=pt++;pt->y=x, pt->n=fir[y], fir[y]=pt++; } int Tree[maxn], Size[maxn], Belong[maxn], Lower[maxn], Deep[maxn], Head[maxn], Where[maxn], cnt, Key[maxn]; int Left[maxp], Right[maxp], sum[maxp], big[maxp], z, L, R; int n, d[maxn], h[maxn], now;void dfs(int x) {int maxs=-inf, maxl=0;travel(x) if (p->y!=h[x]){h[p->y]=x, d[p->y]=d[x]+1; dfs(p->y);if (s(b(p->y))>maxs) maxs=s(b(p->y)), maxl=p->y;}if (maxl)b(x)=b(maxl), w(x)=w(maxl)+1, s(b(x))++, dep(b(x))--;elsecnt++, b(x)=cnt, w(x)=1, s(cnt)=1, low(cnt)=x, dep(cnt)=d[x];travel(x) if (p->y!=h[x] && p->y!=maxl) h(b(p->y))=x; } void BuildT(int&k, int l, int r, int t) {if (l==r){sum[t]=big[t]=k(k), k=h[k]; return;}int mid=(l+r)>>1;BuildT(k, l, mid, l(t)=++z), BuildT(k, mid+1, r, r(t)=++z);sum[t]=sum[l(t)]+sum[r(t)], big[t]=max(big[l(t)], big[r(t)]); } inline void Build() {dfs(1); h(b(1))=0;rep(i, 1, cnt) now=low(i), BuildT(now, 1, s(i), t(i)=++z); }void Edit(int k, int y, int l, int r, int t) {if (l==r){sum[t]=big[t]=y; return;}int mid=(l+r)>>1;if (k<=mid) Edit(k, y, l, mid, l(t)); else Edit(k, y, mid+1, r, r(t));sum[t]=sum[l(t)]+sum[r(t)], big[t]=max(big[l(t)], big[r(t)]); } inline void Change(int x, int y){k(x)=y; Edit(w(x), y, 1, s(b(x)), t(b(x)));}void QueryM(int l, int r, int t) {if (L<=l && r<=R) {now=max(now, big[t]); return;}int mid=(l+r)>>1;if (L<=mid) QueryM(l, mid, l(t));if (mid<R) QueryM(mid+1, r, r(t)); } inline void Qmax(int x, int y) {now=-inf; while (b(x)!=b(y)){if (dep(b(x))<dep(b(y))) swap(x, y);L=w(x), R=s(b(x)), QueryM(1, s(b(x)), t(b(x))), x=h(b(x));}if (d[x]<d[y]) swap(x, y);L=w(x), R=w(y), QueryM(1, s(b(x)), t(b(x)));printf("%d\n", now); } void QueryS(int l, int r, int t) {if (L<=l && r<=R) {now+=sum[t]; return;}int mid=(l+r)>>1;if (L<=mid) QueryS(l, mid, l(t));if (mid<R) QueryS(mid+1, r, r(t)); } inline void Qsum(int x, int y) {now=0; while (b(x)!=b(y)){if (dep(b(x))<dep(b(y))) swap(x, y);L=w(x), R=s(b(x)), QueryS(1, s(b(x)), t(b(x))), x=h(b(x));}if (d[x]<d[y]) swap(x, y);L=w(x), R=w(y), QueryS(1, s(b(x)), t(b(x))); printf("%d\n", now); }int main() {n=read();rep(i, 1, n-1) {int x=read(), y=read(); AddE(x, y);}rep(i, 1, n) k(i)=read();Build();int q=read(); char ch[10];rep(i, 1, q){scanf("%s", ch); int x=read(), y=read();if (ch[1]=='H') Change(x, y);if (ch[1]=='S') Qsum(x, y);if (ch[1]=='M') Qmax(x, y);} }

轉載于:https://www.cnblogs.com/NanoApe/p/4479736.html

總結

以上是生活随笔為你收集整理的BZOJ-1036 [ZJOI2008]树的统计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。