題目：維護一個樹，支持修改邊長，查詢任意兩點間距離。

思路：學習了一下樹鏈剖分，還是看了一陣子才看懂的（大概兩個多小時orz。。。）其實總的來說并不是很難，主要是數組比較多，然后看的那篇博客大概是為了壓縮代碼寫得比較緊湊所以看的不是很明白。樹鏈剖分的比較有技巧性的地方是查詢，如果在一條輕鏈上，每次往上一條邊，如果是在重鏈上，就是區間查詢。樹鏈剖分保證任意路徑上的重鏈和輕鏈條數是logn的，所以總的復雜度就是logn的。這個題是單點更新，所以線段樹方面沒什么難度。

/* *@author: Cwind *http://www.cnblogs.com/Cw-trip/ */ #include <bits/stdc++.h> #define pb push_back #define PB pop_back #define bk back() #define se second #define fs first #define IINF (1<<29) #define sq(x) (x)*(x) #define eps 0.000000001 #define clr(x) memset((x),0,sizeof (x)) using namespace std; typedef long long ll; typedef pair<ll,ll> P;/////Segment Tree const int maxp=1e5; const int maxv=1e4+300; struct Node {int l,r;int val;Node *ch[2]; }pool[maxp]; int ph=0; inline Node *newNode(){Node *n=&pool[ph++];n->val=0;return n; } void seg_build(Node *n,int l,int r){n->l=l,n->r=r;if(r-l<=1) return;int mid=(r+l)/2;n->ch[0]=newNode();n->ch[1]=newNode();seg_build(n->ch[0],l,mid);seg_build(n->ch[1],mid,r); } void seg_update(Node *n,int a,int b,int x){int l=n->l,r=n->r;if(l>=b||r<=a) return;if(r-l<=1){n->val=x;return;}seg_update(n->ch[0],a,b,x);seg_update(n->ch[1],a,b,x);n->val=max(n->ch[0]->val,n->ch[1]->val); } int seg_query(Node *n,int a,int b){int l=n->l,r=n->r;if(l>=b||r<=a) return 0;if(l>=a&&r<=b) return n->val;return max(seg_query(n->ch[0],a,b),seg_query(n->ch[1],a,b)); } Node *root; void seg_init(){ph=0;root=newNode(); }///Tree Cut struct EDGE{int to,d;int id;EDGE(int to,int d,int id):to(to),d(d),id(id){} }; vector<EDGE> G[maxv]; int fa[maxv],dep[maxv],siz[maxv],son[maxv],top[maxv],w[maxv],itow[maxv],sone[maxv]; void dfs1(int v,int d,int f=-1){dep[v]=d;fa[v]=f;siz[v]=1;int maxs=0;son[v]=0;for(int i=0;i<G[v].size();i++){EDGE &e=G[v][i];if(e.to==f) continue;dfs1(e.to,d+1,v);siz[v]+=siz[e.to];if(siz[e.to]>maxs){son[v]=e.to;maxs=siz[e.to];sone[v]=e.id;}} } int dfsn=0; int dd[maxv]; void dfs2(int v,int ff,int from){w[v]=dfsn++;itow[from]=w[v];if(ff==-1) top[v]=v;else top[v]=top[ff];if(son[v])dfs2(son[v],v,sone[v]);for(int i=0;i<G[v].size();i++){EDGE &e=G[v][i];if(e.to==fa[v]||e.to==son[v]) continue;dfs2(e.to,-1,e.id);} } int T,N; void build_tree(){for(int i=1;i<N;i++){seg_update(root,itow[i],itow[i]+1,dd[i]);} }int Query(int a,int b){int f1=top[a],f2=top[b],ans=0;while(f1!=f2){if(dep[f1]>dep[f2]) swap(a,b),swap(f1,f2);ans=max(ans,seg_query(root,w[f2],w[b]+1));b=fa[f2];f2=top[b];}if(a==b) return ans;if(dep[a]>dep[b]) swap(a,b);ans=max(ans,seg_query(root,w[a]+1,w[b]+1));return ans; } char r[maxv]; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);cin>>T;while(T--){cin>>N;for(int i=1;i<=N;i++) G[i].clear();dfsn=0;seg_init();seg_build(root,1,N);for(int i=1;i<=N-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);G[a].pb(EDGE(b,c,i));G[b].pb(EDGE(a,c,i));dd[i]=c;}dfs1(1,0);dfs2(1,-1,0);seg_build(root,1,N);build_tree();for(;;){scanf("%s",r);if(r[0]=='D') break;if(r[0]=='C'){int a,b;scanf("%d%d",&a,&b);seg_update(root,itow[a],itow[a]+1,b);}else{int a,b;scanf("%d%d",&a,&b);printf("%d\n",Query(a,b));}}}return 0; } View Code

ps：t了，差點開始懷疑是線段樹寫挫了。。結果是死循環了。。。

?hdu3966

題目：維護一棵樹上的點權，給某兩點間的路徑上的所有點加上權值x，詢問某個點的點權。

思路：由于是直接詢問點，所以實際上比spoj的那道題好寫，區間和直接用bit維護一下就好了。

/* *@author: Cwind *http://www.cnblogs.com/Cw-trip/ */ #include <bits/stdc++.h> #define pb push_back #define PB pop_back #define bk back() #define se second #define fs first #define IINF (1<<29) #define sq(x) (x)*(x) #define eps 0.000000001 #define clr(x) memset((x),0,sizeof (x)) using namespace std; typedef long long ll; typedef pair<ll,ll> P;const int maxn=5e4+300; int N,M,O; int a[maxn]; vector<int> G[maxn]; /////Tree Cut int fa[maxn],dep[maxn],son[maxn],top[maxn],siz[maxn],tw[maxn]; void dfs1(int v,int d=0,int f=-1){fa[v]=f;siz[v]=1;dep[v]=d;son[v]=0;int ma=0;for(int i=0;i<G[v].size();i++){int u=G[v][i];if(u==f) continue;dfs1(u,d+1,v);siz[v]+=siz[u];if(siz[u]>ma){ma=siz[u];son[v]=u;}} } int dfsn=0; void dfs2(int v){if(fa[v]==-1) top[v]=v;tw[v]=++dfsn;if(son[v]){top[son[v]]=top[v];dfs2(son[v]);}for(int i=0;i<G[v].size();i++){int u=G[v][i];if(u==fa[v]||u==son[v]) continue;top[u]=u;dfs2(u);} } /BIT const int maxB=maxn*2; struct BIT{int a[maxB],b[maxB];void clear(){memset(a,0,sizeof a);memset(b,0,sizeof b);}void add(int *A,int p,int x){while(p<maxB){A[p]+=x;p+=p&-p;}}int sum(int *A,int p){int ans=0;while(p){ans+=A[p];p-=p&-p;}return ans;}void seg_add(int l,int r,int x){add(a,l,-x*(l-1));add(b,l,x);add(a,r+1,x*r);add(b,r+1,-x);}int get(int p){int s1=sum(b,p-1)*(p-1)+sum(a,p-1);int s2=sum(b,p)*(p)+sum(a,p);return s2-s1;} }B;void update(int v1,int v2,int x){int f1=top[v1],f2=top[v2];while(f1!=f2){if(dep[f1]>dep[f2]) swap(v1,v2),swap(f1,f2);B.seg_add(tw[f2],tw[v2],x);v2=fa[f2],f2=top[v2];}if(dep[v1]>dep[v2]) swap(v1,v2);B.seg_add(tw[v1],tw[v2],x); } char r[10]; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);while(cin>>N>>M>>O){dfsn=0;B.clear();for(int i=0;i<maxn;i++)G[i].clear();for(int i=1;i<=N;i++)scanf("%d",&a[i]);for(int i=0;i<M;i++){int u,v;scanf("%d%d",&u,&v);G[u].pb(v);G[v].pb(u);}dfs1(1);dfs2(1);for(int i=1;i<=N;i++)B.seg_add(tw[i],tw[i],a[i]);while(O--){scanf("%s",r);int a,b,c;if(r[0]=='I'){scanf("%d%d%d",&a,&b,&c);update(a,b,c);}else if(r[0]=='D'){scanf("%d%d%d",&a,&b,&c);update(a,b,-c);}else{scanf("%d",&a);printf("%d\n",B.get(tw[a]));}}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/Cw-trip/p/4783758.html

總結

以上是生活随笔為你收集整理的SPOJ- QTREE+HDU 3966（树链剖分裸题的全部內容，希望文章能夠幫你解決所遇到的問題。

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